https://leetcode.com/problems/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:
intervalswill have length in range[1, 3000].intervals[i]will have length2, representing some integer interval.intervals[i][j]will be an integer in[0, 10^8].
https://leetcode.com/problems/set-intersection-size-at-least-two/discuss/113085/Ever-wonder-why-the-greedy-algorithm-works-Here-is-the-explanation!
http://www.programmersought.com/article/2997206267/
https://leetcode.com/articles/set-intersection-size-at-least-two/
Let's try to solve a simpler problem: what is the answer when the set intersection size is at least one?
Sort the points. Take the last interval
[s, e], which point on this interval will be in S? Since every other interval has start point <= s, it is strictly better to choose s as the start. So we can repeatedly take s in our set S and remove all intervals containing s.
We will try to extend this solution to the case when we want an intersection of size two.
Algorithm
For each interval, we will perform the algorithm described above, storing a
todo multiplicity which starts at 2. As we identify points in S, we will subtract from these multiplicities as appropriate.
One case that is important to handle is the following:
[[1, 2], [2, 3], [2, 4], [4, 5]]. If we put 4, 5 in S, then we put 2 in S, when handling [2, 3] we need to put 3 in S, not 2 which was already put.
We can handle this case succinctly by sorting intervals
[s, e] by s ascending, then e descending. This makes it so that any interval encountered with the same s has the lowest possible e, and so it has the highest multiplicity. When at interval [s, e] and choosing points to be included into S, it will always be the case that the start of the interval (either s or s, s+1) will be unused.public int intersectionSizeTwo(int[][] intervals) { Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0]-b[0] : b[1]-a[1]); int[] todo = new int[intervals.length]; Arrays.fill(todo, 2); int ans = 0, t = intervals.length; while (--t >= 0) { int s = intervals[t][0]; int e = intervals[t][1]; int m = todo[t]; for (int p = s; p < s+m; ++p) { for (int i = 0; i <= t; ++i) if (todo[i] > 0 && p <= intervals[i][1]) todo[i]--; ans++; } } return ans; }
https://leetcode.com/problems/set-intersection-size-at-least-two/discuss/113086/Hope-you-enjoy-this-problem.-%3A-)-O(NlogN)JavaGreedy-Easy-to-understand-solution
- Sort the array according to their end point in ascending order, AND if two intervals have same end, sort them according to their start point in descending order. e.g [[1,5],[4,5],[5,9],[7,9],[9,10]] => [[4,5], [1,5], [7,9], [5,9] , [9,10]]
- Greedy to get the rightmost two point
public int intersectionSizeTwo(int[][] intervals) {
int res = 0;
if (intervals == null || intervals.length == 0) {
return res;
}
Arrays.sort(intervals, (a, b)-> a[1] != b[1] ? a[1] - b[1] : b[0] - a[0]);
// known two rightmost point in the set/res
int left = intervals[0][1] - 1;
int right = intervals[0][1];
res += 2;
for (int i = 1; i < intervals.length; i++) {
int[] curr = intervals[i];
// 1. one element of the set is in the interval
// 2. no elemnet of the set is in the interval
if (left < curr[0] && curr[0] <= right) {
res++;
left = right;
right = curr[1];
} else if (curr[0] > right) {
res += 2;
left = curr[1] - 1;
right = curr[1];
}
}
return res;
}
First sort the intervals, with their starting points from low to high
Then use a stack to eliminate the intervals which fully overlap another interval.
For example, if we have [2,9] and [1,10], we can get rid of [1,10]. Because as long as we pick up two numbers in [2,9], the requirement for [1,10] can be achieved automatically.
Then use a stack to eliminate the intervals which fully overlap another interval.
For example, if we have [2,9] and [1,10], we can get rid of [1,10]. Because as long as we pick up two numbers in [2,9], the requirement for [1,10] can be achieved automatically.
Finally we deal with the sorted intervals one by one.
(1) If there is no number in this interval being chosen before, we pick up 2 biggest number in this interval. (the biggest number have the most possibility to be used by next interval)
(2) If there is one number in this interval being chosen before, we pick up the biggest number in this interval.
(3) If there are already two numbers in this interval being chosen before, we can skip this interval since the requirement has been fulfilled.
(1) If there is no number in this interval being chosen before, we pick up 2 biggest number in this interval. (the biggest number have the most possibility to be used by next interval)
(2) If there is one number in this interval being chosen before, we pick up the biggest number in this interval.
(3) If there are already two numbers in this interval being chosen before, we can skip this interval since the requirement has been fulfilled.
public int intersectionSizeTwo(int[][] intervals) {
Arrays.sort(intervals,(a,b)->((a[0]==b[0])?(-a[1]+b[1]):(a[0]-b[0])));
Stack<int[]> st=new Stack<>();
for (int[] in:intervals)
{
while (!st.isEmpty() && st.peek()[1]>=in[1]) st.pop();
st.push(in);
}
int n=st.size();
int[][] a=new int[n][2];
for (int i=n-1;i>=0;i--)
{
a[i][0]=st.peek()[0];
a[i][1]=st.pop()[1];
}
int ans=2;
int p1=a[0][1]-1,p2=a[0][1];
for (int i=1;i<n;i++)
{
boolean bo1=(p1>=a[i][0] && p1<=a[i][1]),bo2=(p2>=a[i][0] && p2<=a[i][1]);
if (bo1 && bo2) continue;
if (bo2)
{
p1=p2;
p2=a[i][1];
ans++;
continue;
}
p1=a[i][1]-1;
p2=a[i][1];
ans+=2;
}
return ans;
}
一个区间[a, b]表示a到b的所有整数（包括a, b），找出最小数量的整数集合S，使得S和每个区间相交的整数个数大于等于2，返回S集合中整数的个数。例如对于区间[1, 3]、[2, 4]，S = {2， 3}，即答案为2。
https://www.cnblogs.com/grandyang/p/8503476.html
这道题给了我们一些区间，让我们求一个集合S，使得S和每个区间的交集至少为2，即至少有两个相同的数字。博主最开始分析题目中的例子的时候，以为要求的集合S也必须是一个连续的区间，其实不需要的，离散的数字就可以了。比如如果区间是[1,3], [5,6]的话，那么返回的集合长度是4，而不是5。这道题可以是用贪婪算法来解，一般来说Hard的题目能用贪婪算法而不是DP解的是少之又少，这道题为我大Greedy算法正名了～！为了使得集合S中的数字尽可能的小，我们希望处理区间的时候从小区间开始，如果区间b完全覆盖了区间a，那么和区间a有两个相同数字的集合，一定和区间b也有两个相同数字。同样，我们不希望一会处理一个前面的区间，一会又处理一个很后面的区间，我们希望区间是有序的。那么如何给区间排序呢，是按起始位置排，还是按结束位置排，这里我们按结束位置从小往大排，当两个结束位置相同时，起始位置大的排前面先处理，这也符合我们先处理小区间的原则。那么遍历区间的时候，当前区间就和我们维护的集合S有三种情况：
1. 二者完全没有交集，这时候我们就需要从当前区间中取出两个数字加入集合S，取哪两个数呢？为了尽可能少使用数字，我们取当前区间中的最大两个数字，因为我们区间位置不断变大，所以取大的数字有更高的概率能和后面的区间有交集。
2. 二者有一个数字的交集，那么这个交集数字一定是区间的起始位置，那么我们需要从当前区间中再取一个数字加入集合S，根据上面的分析，我们取最大的那个数，即区间的结束位置。
3. 二者有两个及两个以上数字的交集，那么不用做任何处理。
好，分析到这里，代码也就不难写出来了，我们用个数组v来表示集合S，初始化放两个-1进去，因为题目中说明了区间都是大于0的，所以我们放这两个数组进去是为了防止越界的，不会有任何影响，最后统计长度的时候减去这个两个数字就可以了。先给区间排序，然后遍历每个区间，如果区间的起始位置小于等于数组的倒数第二个数字，说明此时已经有两个相同的数字了，直接跳过当前区间。否则如果区间的起始位置大于数组的最后一个位置，说明二者没有任何交集，我们此时先把区间的倒数第二小的数字加入数组v中。然后统一再把区间的结束位置加入数组v中，因为不管区间和数组有一个交集还是没有任何交集，结束位置都要加入数组中，所以不用放在if..else..中。最后循环结束，返回数组的大小减2
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; }
我们可以对空间复杂度进行优化，我们不用保存整个集合S，因为结果只让我们返回长度即可，所以我们用两个变量p1和p2，其中p1表示集合S中倒数第二大的数字，p2为集合S中最大的数字。我们的整个逻辑跟上面的解法是相同的。遍历区间的时候，如果区间的起始位置小于等于p1，则跳过当前区间。否则如果起始位置大于p2，说明没有交集，需要加上两个数字，结果res自增2，然后p2赋值为当前区间的结束位置，p1赋值为第二大的数字。否则说明只有一个交集，结果res自增1，然后p1赋值为p2，p2赋值为当前区间的结束位置即可
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; }
讨论：这道题的一个拓展就是一般化，改为交集大小至少为k，那么我们该怎么做呢？其实也不是很难，我们可以在解法一的基础上进行修改，我们还是用数组v来表示集合S，只不过我们初始化加入k个-1。然后还是要给区间排序，之后进行遍历，如果起始位置小于等于倒数第k个数，跳过当前区间。然后就是重点部分了，我们还是用起始位置跟数组v的最后面的数字比较，总共比到倒数第k-1个数就行了，因为小于等于倒数第k个数已经跳过了。如果大于最后一个数，则将区间后k个数加入数组；否则如果大于倒数第二个数，则将区间后k-1个数加入数组；否则如果大于倒数第三个数，则将数组后k-2个数加入数组，以此类推，直到比完倒数第k-1个数就行了，最后返回的是数组v的长度减去k。
这道题我们可以观察出如下几点，对于两个区间i1和i2：
- 如果区间i1包含区间i2，那么我们可以直接将remove i1而不需要考虑它，因为最终结果i2肯定至少也有两个元素被选，那么i1肯定也满足条件
- 如果i1和i2没有交集，那么两个区间各自取两个数
- 如果i1和i2正好头尾相交，比如i1 = [1,3], i2 = [3,6]，那么我们只需要在交点处取一个，之后在i1和i2中各取一个
- 如果i2和i2相交并且相交的区间大于等于2，我们只需要在相交的部分取两个即可
对于情况1，我们只需要做一个preprocess，用stack来帮我们remove包含的情况。具体做法是，我们按照start排序interval，如果当前栈顶元素i1.end 大于等于当前元素i2.end，我们pop出i1即可。这样可以保证我们不会出现1中情况。那么现在的问题是，对于2、3、4的情况，我们应该如何在区间中取数呢？
经过preprocess之后，现在已经不存在1的情况，我们按照start排序，然后依次取出interval。如果我们发现需要在当前区间取数，那么我们取尽量靠右边的数，这样的话，对于下一个区间，其能够重复利用的可能性是最大的。也就说，假设已经在i1中取了数并且满足题目要求，对于i2来说：
- 如果是情况2，我们在i2的最右端取两个数
- 如果是情况2和3：
- 假设区间覆盖的部分没有包含i1取的数，同情况2
- 假设区间覆盖的部分包含i1取的数：
- 如果包含了1个，在i2最右端取一个
- 如果包含了2个，i2就不要取了
也就是说，我们每次要记录并更新上一次取的两个数的位置。假设有n个区间，算法时间复杂度O(n * log n)，空间复杂度O(n)
The Original problem I contributed asked for all the elements of the qualified set, but the idea is same. This is for original question
class Interval {
int start;
int end;
Interval() { start = 0; end = 0; }
Interval(int s, int e) { start = s; end = e; }
}
public List<Integer> findSet(List<Interval> intervals) {
List<Integer> res = new ArrayList<>();
if (intervals == null || intervals.size() == 0) {
return res;
}
Collections.sort(intervals, (a, b)-> a.end != b.end ? a.end - b.end : b.start - a.start);
int left = intervals.get(0).end - 1;
int right = intervals.get(0).end;
res.add(left);
res.add(right);
for (int i = 1; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
// 1. one element of the set is in the interval
// 2. no elemnet of the set is in the interval
if (left < curr.start && curr.start <= right) {
res.add(curr.end);
left = right;
right = curr.end;
} else if (curr.start > right) {
res.add(curr.end - 1);
res.add(curr.end);
left = curr.end - 1;
right = curr.end;
}
}
return res;
}
