2022-08-20：给定区间的范围[xi,yi]，xi<=yi，且都是正整数，
找出一个坐标集合set，set中有若干个数字，
set要和每个给定的区间，有交集。
求set的最少需要几个数。
比如给定区间 : [5, 8] [1, 7] [2, 4] [1, 9]，
set最小可以是: {2, 6}或者{2, 5}或者{4, 5}。
答案2022-08-20：
生成事件，排序，遍历事件获得结果。
代码用rust编写。代码如下：
代码语言：javascript复制use std::collections::HashSet;
fn main() {
let mut arr: Vec<Vec<i32>> = vec![vec![5, 8], vec![1, 7], vec![2, 4], vec![1, 9]];
let ans1 = min_set(&mut arr);
println!("ans1 = {}", ans1);
}
fn min_set(ranges: &mut Vec<Vec<i32>>) -> i32 {
let n = ranges.len() as i32;
// events[i] = {a, b, c}
// a == 0, 表示这是一个区间的开始事件，这个区间结束位置是b
// a == 1, 表示这是一个区间的结束事件，b的值没有意义
// c表示这个事件的时间点，不管是开始事件还是结束事件，都会有c这个值
let mut events: Vec<Vec<i32>> = vec![];
for i in 0..n << 1 {
events.push(vec![]);
for _ in 0..3 {
events[i as usize].push(0);
}
}
for i in 0..n {
// [3, 7]
// (0,7,3)
// (1,X,7)
events[i as usize][0] = 0;
events[i as usize][1] = ranges[i as usize][1];
events[i as usize][2] = ranges[i as usize][0];
events[(i n) as usize][0] = 1;
events[(i n) as usize][2] = ranges[i as usize][1];
}
events.sort_by(|a, b| a[2].cmp(&b[2]));
// 容器
let mut tmp: HashSet<i32> = HashSet::new();
let mut ans = 0;
for event in events.iter() {
if event[0] == 0 {
tmp.insert(event[1]);
} else {
if tmp.contains(&event[2]) {
ans = 1;
tmp.clear();
}
}
}
return ans;
}
执行结果如下：
***
