2022-10-11：一个整数区间 [a, b] ( a ＜ b ) 代表着从 a 到 b 的所有连续整数，包括 a 和 b。 给你一组整数区间intervals，请找到一个最小的集合 S， 使得

2022-10-11：一个整数区间 [a, b] ( 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编写。代码如下：

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代码

2022-10-11：一个整数区间 [a, b] ( a ＜ b ) 代表着从 a 到 b 的所有连续整数，包括 a 和 b。 给你一组整数区间intervals，请找到一个最小的集合 S， 使得的相关教程结束。