# 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].

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```

346 篇文章47 人订阅

0 条评论