757. Set Intersection Size At Least Two

An integer interval `[a, b]` (for integers `a < b`) is a set of all consecutive integers from `a` to `b`, including `a` and `b`.

Find the minimum size of a set S such that for every integer interval A in `intervals`, the intersection of S with A has size at least 2.

Example 1:

``````Input: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
Output: 3
Explanation:
Consider the set S = {2, 3, 4}.  For each interval, there are at least 2 elements from S in the interval.
Also, there isn't a smaller size set that fulfills the above condition.
Thus, we output the size of this set, which is 3.
``````

Example 2:

``````Input: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]
Output: 5
Explanation:
An example of a minimum sized set is {1, 2, 3, 4, 5}.
``````

Note:

1. `intervals` will have length in range `[1, 3000]`.
2. `intervals[i]` will have length `2`, representing some integer interval.
3. `intervals[i][j]` will be an integer in `[0, 10^8]`.

1. 二者完全没有交集，这时候我们就需要从当前区间中取出两个数字加入集合S，取哪两个数呢？为了尽可能少使用数字，我们取当前区间中的最大两个数字，因为我们区间位置不断变大，所以取大的数字有更高的概率能和后面的区间有交集。

2. 二者有一个数字的交集，那么这个交集数字一定是区间的起始位置，那么我们需要从当前区间中再取一个数字加入集合S，根据上面的分析，我们取最大的那个数，即区间的结束位置。

3. 二者有两个及两个以上数字的交集，那么不用做任何处理。

``````class Solution {
public:
int intersectionSizeTwo(vector<vector<int>>& intervals) {
vector<int> v{-1, -1};
sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){
return a[1] < b[1] || (a[1] == b[1] && a[0] > b[0]);
});
for (auto &interval : intervals) {
int len = v.size();
if (interval[0] <= v[len - 2]) continue;
if (interval[0] > v.back()) v.push_back(interval[1] - 1);
v.push_back(interval[1]);
}
return v.size() - 2;
}
};
``````

``````class Solution {
public:
int intersectionSizeTwo(vector<vector<int>>& intervals) {
int res = 0, p1 = -1, p2 = -1;
sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){
return a[1] < b[1] || (a[1] == b[1] && a[0] > b[0]);
});
for (auto &interval : intervals) {
if (interval[0] <= p1) continue;
if (interval[0] > p2) {
res += 2;
p2 = interval[1];
p1 = p2 - 1;
} else {
++res;
p1 = p2;
p2 = interval[1];
}
}
return res;
}
};
``````

https://leetcode.com/problems/set-intersection-size-at-least-two/discuss/117545/C++-sort-and-greedy-10-lines

https://leetcode.com/problems/set-intersection-size-at-least-two/discuss/113089/C++-concise-solution-O(nlogn)-greedy-39-ms

https://leetcode.com/problems/set-intersection-size-at-least-two/discuss/113085/Ever-wonder-why-the-greedy-algorithm-works-Here-is-the-explanation!

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation