2022-08-20：给定区间的范围[xi,yi]，xi＜=yi，且都是正整数， 找出一个坐标集合set，set中有若干

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编写。代码如下：

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;
}

执行结果如下：

左神java代码

本作品采用《CC 协议》，转载必须注明作者和本文链接