2022-08-20：给定区间的范围[xi,yi]，xi＜=yi，且都是正整数， 找出一个坐标集合set，set中有若干个数字， 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代码

2022-08-20：给定区间的范围[xi,yi]，xi＜=yi，且都是正整数， 找出一个坐标集合set，set中有若干个数字， set要和每个给定的区间，有交集。 求set的最少需要几个数。 比如给的相关教程结束。