Set Intersection Size At Least Two
Set Intersection Size At Least Two
LWC 65: 757. Set Intersection Size At Least Two
Problem:
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:
- intervals will have length in range [1, 3000].
- intervals[i] will have length 2, representing some integer interval.
- intervals[i][j] will be an integer in [0, 10^8].
思路： 在选择区间中的元素时，我们可以随意选， 但随意选的后果是不能让set最优，所以可以从侧面反映出如果有【规则】的选择，可能达到全局最优。一个思路：对end进行排序，这样我们就能根据end进行规则的选择了。 1. 很明显，对于待选区间，如果之前没有元素被选择过，那么一定选择最后两个元素，这样能够覆盖的后续区间最多，不过此时需要判断一下，选择两个元素之后，后续区间是否都包含该两个元素。包含一个+1， 包含两个+2，不包含则跳出。 2. 对于一个元素被选择了，我们依旧选取当前区间的最后一个元素，不过此时只选择了一个，所以只需要测试后续区间是否包含该元素即可。
Java版本：
class P implements Comparable<P>{
int s;
int e;
int c;
P(int s, int e){
this.s = s;
this.e = e;
this.c = 0;
}
@Override
public int compareTo(P o) {
return this.e - o.e;
}
}
public int intersectionSizeTwo(int[][] intervals) {
List<P> ps = new ArrayList<>();
int n = intervals.length;
for (int i = 0; i < n; ++i) {
ps.add(new P(intervals[i][0], intervals[i][1]));
}
Collections.sort(ps);
int ans = 0;
for (int i = 0; i < n; ++i) {
P inter = ps.get(i);
if (inter.c == 0) {
int pos = i + 1;
while (pos < n && ps.get(pos).s <= inter.e) {
ps.get(pos).c ++;
if (ps.get(pos).s < inter.e) {
ps.get(pos).c ++;
}
pos ++;
}
ans += 2;
}
else if (inter.c == 1){
int pos = i + 1;
while (pos < n && ps.get(pos).s <= inter.e) {
ps.get(pos).c ++;
pos ++;
}
ans ++;
}
}
return ans;
}Python版本：
def intersectionSizeTwo(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: int
"""
intervals.sort(key = lambda x : x[1])
n = len(intervals)
cnt = [0] * n
ans = 0
for i in range(n):
interval = intervals[i]
if cnt[i] == 0:
pos = i + 1
while pos < n and intervals[pos][0] <= interval[1]:
cnt[pos] += 1
if (intervals[pos][0] < interval[1]):
cnt[pos] += 1
pos += 1
ans += 2
elif cnt[i] == 1:
pos = i + 1
while pos < n and intervals[pos][0] <= interval[1]:
cnt[pos] += 1
pos += 1
ans += 1
return ans该问题的切入点：明确每个区间都需要选择两个元素，这样就能找到选取元素的可能准则了。