2022-10-11：一个整数区间 a, b 代表着从 a 到 b 的所有连续整数，包括 a 和 b。
给你一组整数区间intervals，请找到一个最小的集合 S，
使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。
输出这个最小集合S的大小。
输入: intervals = [1, 2, 2, 3, 2, 4, 4, 5]。
输出: 5。
答案2022-10-11：
力扣757。
贪心。先按结尾数字升序排序，再按开始数字降序排序。
第一个整数区间，先选靠后的两个数字。
java，go，rust运行情况见截图。java和go运行最快，go运行速度落后了。内存占用上，rust占用内存最少，go次之，java最高。
代码用rust编写。代码如下：
代码语言：rust复制impl Solution {
pub fn intersection_size_two(intervals: Vec<Vec<i32>>) -> i32 {
let mut intervals = intervals;
// O(N*logN)
// 区间根据，结束位置谁小，谁在前
// 结束位置一样的，开头位置谁大，谁在前
intervals.sort_by(|a, b| {
if a[1] != b[1] {
a[1].cmp(&b[1])
} else {
b[0].cmp(&a[0])
}
});
// 区间排好序了
// [1,7] [2,8] [1,8] [13,40]
let n = intervals.len() as i32;
// [1,7] pre = 6 pos =7
let mut pos = intervals[0][1];
let mut pre = pos - 1;
let mut ans = 2;
for i in 1..n {
// intervals[i] = {开头，结尾}
// 6 7 [<=6, 结尾]
//
// if(intervals[i][0] <= pre) {
// continue;
// }
// >6 讨论！
if intervals[i as usize][0] > pre {
// 6 7 [开头>6, 结尾]
// 1) 6 < 开头 <= 7
// 只有7满足了当前的区间，我们要加个数字，结尾
// 6 7 结尾
// pre pos
// 6 7
// 2) 6 < 开头、7 < 开头
// 结尾-1 结尾
// pre pos
if intervals[i as usize][0] > pos {
// 对应的就是情况2)
pre = intervals[i as usize][1] - 1;
ans = 2;
} else {
// 对应的就是情况1)
pre = pos;
ans = 1;
}
// 不管情况2)还是情况1)都需要这一句
pos = intervals[i as usize][1];
}
}
return ans;
}
}
fn main() {
let rectangles = vec![vec![1, 2], vec![2, 3], vec![2, 4], vec![4, 5]];
let ans = Solution::intersection_size_two(rectangles);
println!("ans = {:?}", ans);
}
struct Solution {}执行结果如下：
在这里插入图片描述
在这里插入图片描述左神java代码
