写点什么

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

  • 2022 年 10 月 11 日
    北京
  • 本文字数:1249 字

    阅读完需:约 4 分钟

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

发布于: 刚刚阅读数: 4
用户头像

还未添加个人签名 2021.02.15 加入

还未添加个人简介

评论

发布
暂无评论
2022-10-11:一个整数区间 [a, b] ( a < b ) 代表着从 a 到 b 的所有连续整数,包括 a 和 b。 给你一组整数区间intervals,请找到一个最小的集合 S, 使得_算法_福大大架构师每日一题_InfoQ写作社区