给你一个二维整数数组 intervals
,其中 intervals[i] = [starti, endi]
表示从 starti
到 endi
的所有整数,包括 starti
和 endi
。
包含集合 是一个名为 nums
的数组,并满足 intervals
中的每个区间都 至少 有 两个 整数在 nums
中。
- 例如,如果
intervals = [[1,3], [3,7], [8,9]]
,那么[1,2,4,7,8,9]
和[2,3,4,8,9]
都符合 包含集合 的定义。
返回包含集合可能的最小大小。
示例 1:
输入:intervals = [[1,3],[3,7],[8,9]] 输出:5 解释:nums = [2, 3, 4, 8, 9]. 可以证明不存在元素数量为 4 的包含集合。
示例 2:
输入:intervals = [[1,3],[1,4],[2,5],[3,5]] 输出:3 解释:nums = [2, 3, 4]. 可以证明不存在元素数量为 2 的包含集合。
示例 3:
输入:intervals = [[1,2],[2,3],[2,4],[4,5]] 输出:5 解释:nums = [1, 2, 3, 4, 5]. 可以证明不存在元素数量为 4 的包含集合。
提示:
1 <= intervals.length <= 3000
intervals[i].length == 2
0 <= starti < endi <= 108
方法一:排序 + 贪心
相似题目: 452. 用最少数量的箭引爆气球
class Solution:
def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: (x[1], -x[0]))
s = e = -1
ans = 0
for a, b in intervals:
if a <= s:
continue
if a > e:
ans += 2
s, e = b - 1, b
else:
ans += 1
s, e = e, b
return ans
class Solution {
public int intersectionSizeTwo(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] == b[1] ? b[0] - a[0] : a[1] - b[1]);
int ans = 0;
int s = -1, e = -1;
for (int[] v : intervals) {
int a = v[0], b = v[1];
if (a <= s) {
continue;
}
if (a > e) {
ans += 2;
s = b - 1;
e = b;
} else {
ans += 1;
s = e;
e = b;
}
}
return ans;
}
}
class Solution {
public:
int intersectionSizeTwo(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [&](vector<int>& a, vector<int>& b) {
return a[1] == b[1] ? a[0] > b[0] : a[1] < b[1];
});
int ans = 0;
int s = -1, e = -1;
for (auto& v : intervals) {
int a = v[0], b = v[1];
if (a <= s) continue;
if (a > e) {
ans += 2;
s = b - 1;
e = b;
} else {
ans += 1;
s = e;
e = b;
}
}
return ans;
}
};
func intersectionSizeTwo(intervals [][]int) int {
sort.Slice(intervals, func(i, j int) bool {
a, b := intervals[i], intervals[j]
if a[1] == b[1] {
return a[0] > b[0]
}
return a[1] < b[1]
})
ans := 0
s, e := -1, -1
for _, v := range intervals {
a, b := v[0], v[1]
if a <= s {
continue
}
if a > e {
ans += 2
s, e = b - 1, b
} else {
ans += 1
s, e = e, b
}
}
return ans
}