包含每个查询的最小区间
思路
先讲最简单的,无脑线段树更新区间最小值即可。
但是区间的值域是 1e7,线段树肯定是不行,但是并查集可以。
我们先按区间长度来排序这些区间,然后遍历每个区间,更新他们对应的值即可,可以利用并查集来快速跳过已经设置好值的点。
题解的优先队列做法感觉不太好想,但是复杂度确实更优秀,这题值域要是 1e9 我这个做法就不行了。算是优雅一点的暴力吧。
int fa[10000005], f[10000005];
class Solution {
public:
int getf(int x) {
if (fa[x] == x) return x;
return fa[x] = getf(fa[x]);
}
vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
sort(intervals.begin(), intervals.end(), [](vector<int> &x, vector<int> &y){
return x.back() - x[0] < y.back() - y[0];
});
int ma = 1;
for (auto &a : intervals) {
ma = max(ma, a.back());
}
for (int i = 1; i <= ma; i++) {
fa[i] = i;
f[i] = 1e9;
}
for (auto &a : intervals) {
int len = a.back() - a[0] + 1;
// cout << a[0] << " " << a.back() << "\n";
for (int i = a[0]; i <= a.back(); i++) {
if (f[i] < 1e8) {
i = getf(i);
continue;
}
f[i] = min(f[i], len);
// cout << "f[" << i << "] = " << f[i] << "\n";
fa[i] = a.back();
}
}
vector<int> ans;
for (auto &val : queries) {
if (f[val] < 1e8) {
ans.emplace_back(f[val]);
}
else {
ans.emplace_back(-1);
}
}
return ans;
}
};
突然翻到这篇题解 灵茶山艾府的题解,他也用了并查集,但是是对于查询数组长度大小的,感觉也是个很不错的做法。