757.设置交集大小至少为2

链接：757.设置交集大小至少为2
难度：Hard
标签：贪心、数组、排序
简介：输出这个最小集合 S 的大小。

题解 1 - cpp

• 编辑时间：2022-07-22
• 执行用时：212ms
• 内存消耗：55MB
• 编程语言：cpp
• 解法介绍：贪心,排序后对于两个区间进行假定,如果无交集则说明集合数加二,如果包容则说明只需考虑最小区间。

class Solution {
   public:
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(),
             [&](vector<int> a, vector<int> b) -> bool {
                 return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
             });
        int n = intervals.size(), l = intervals[n - 1][0], r = l + 1, ans = 2;
        for (int i = n - 2; i >= 0; i--) {
            if (intervals[i][1] >= r)
                continue;
            else if (intervals[i][1] < l) {
                ans += 2;
                l = intervals[i][0];
                r = l + 1;
            } else {
                r = l;
                l = intervals[i][0];
                ans++;
            }
        }
        return ans;
    }
};

题解 2 - rust

• 编辑时间：2022-07-22
• 执行用时：4ms
• 内存消耗：2.3MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn intersection_size_two(intervals: Vec<Vec<i32>>) -> i32 {
        let mut intervals = intervals;
        intervals.sort_by(|v1, v2| {
            if v1[0] == v2[0] {
                v2.cmp(v1)
            } else {
                v1.cmp(v2)
            }
        });
        let n = intervals.len() as i32;
        let mut l = intervals[(n - 1) as usize][0];
        let mut r = l + 1;
        let mut ans = 2;
        let mut i = n - 2;
        while i >= 0 {
            if intervals[i as usize][1] >= r {
                i -= 1;
                continue;
            } else if intervals[i as usize][1] < l {
                l = intervals[i as usize][0];
                r = l + 1;
                ans += 2;
            } else {
                r = l;
                l = intervals[i as usize][0];
                ans += 1;
            }
            i -= 1;
        }
        ans
    }
}