05 August 2008
一个整数区间 [a, b] ( a < b ) 代表着从 a 到 b 的所有连续整数，包括 a 和 b。
给你一组整数区间intervals，请找到一个最小的集合 S，使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。
输出这个最小集合S的大小。
1
2
3
4
5
输入: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
输出: 3
解释:
考虑集合 S = {2, 3, 4}. S与intervals中的四个区间都有至少2个相交的元素。
且这是S最小的情况，故我们输出3。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
/*
最开始数字是0，第i步可以+i或者-i，求最少需要步到达target
https://leetcode.com/problems/set-intersection-size-at-least-two/discuss/113076/Java-O(nlogn)-Solution-Greedy
*/
public int intersectionSizeTwo(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> ((a[0] == b[0]) ? (-a[1] + b[1]) : (a[0] - b[0])));
Stack<int[]> stack = new Stack<>();
for (int[] interval : intervals) {
while (!stack.isEmpty() && stack.peek()[1] >= interval[1]) {
stack.pop();
}
stack.push(interval);
}
int len = stack.size();
int[][] a = new int[len][2];
for (int i = len - 1; i >= 0; i--) {
a[i][0] = stack.peek()[0];
a[i][1] = stack.pop()[1];
}
int result = 2;
int p1 = a[0][1] - 1, p2 = a[0][1];
for (int i = 1; i < len; 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];
result++;
continue;
}
p1 = a[i][1] - 1;
p2 = a[i][1];
result += 2;
}
return result;
}
}