Hard

题目描述

给你一个二维整数数组 intervals，其中 intervals[i] = [starti, endi] 表示从 starti 到 endi（包含端点）的所有整数。

包含集合 是一个数组 nums，使得 intervals 中的每个区间都至少包含 nums 中的两个整数。

例如，如果 intervals = [[1,3], [3,7], [8,9]]，那么 [1,2,4,7,8,9] 和 [2,3,4,8,9] 都是包含集合。

返回包含集合的最小可能大小。

示例 1：

输入：intervals = [[1,3],[3,7],[8,9]]
输出：5
解释：令 nums = [2, 3, 4, 8, 9]。
可以证明不存在大小为 4 的包含数组。

示例 2：

输入：intervals = [[1,3],[1,4],[2,5],[3,5]]
输出：3
解释：令 nums = [2, 3, 4]。
可以证明不存在大小为 2 的包含数组。

示例 3：

输入：intervals = [[1,2],[2,3],[2,4],[4,5]]
输出：5
解释：令 nums = [1, 2, 3, 4, 5]。
可以证明不存在大小为 4 的包含数组。

提示：

  • 1 <= intervals.length <= 3000
  • intervals[i].length == 2
  • 0 <= starti < endi <= 10^8

解题思路

这是一个经典的贪心算法问题。核心思路是通过合理的排序和贪心策略来最小化包含集合的大小。

解题思路：

  1. 排序策略：按区间右端点升序排序，右端点相同时按左端点降序排序。这样确保我们优先处理右端点较小的区间，为后续区间留下更多选择空间。

  2. 贪心选择：维护当前选择的最后两个数字 p1 和 p2（其中 p1 < p2）。对于每个区间，检查已选择的数字是否满足要求：

    • 如果 p1 和 p2 都在当前区间内：无需添加新数字
    • 如果只有 p2 在当前区间内：需要添加一个新数字（区间右端点）
    • 如果 p1 和 p2 都不在当前区间内：需要添加两个新数字（区间右端点的前一个数和右端点）

  3. 边界处理：初始状态下，设置 p1 和 p2 为不可能的值，确保第一个区间会正确添加两个数字。

这个贪心策略的正确性在于：选择尽可能靠右的数字可以最大化与后续区间的重叠可能性，从而最小化总的选择数量。

代码实现

class Solution {
public:
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1] || (a[1] == b[1] && a[0] > b[0]);
        });
        
        int p1 = -1, p2 = -1;
        int result = 0;
        
        for (const auto& interval : intervals) {
            int start = interval[0], end = interval[1];
            
            if (start > p2) {
                // 需要添加两个新数字
                result += 2;
                p1 = end - 1;
                p2 = end;
            } else if (start > p1) {
                // 需要添加一个新数字
                result += 1;
                p1 = p2;
                p2 = end;
            }
            // 否则当前区间已经被覆盖，无需添加
        }
        
        return result;
    }
};

class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[1], -x[0]))
        
        p1, p2 = -1, -1
        result = 0
        
        for start, end in intervals:
            if start > p2:
                # 需要添加两个新数字
                result += 2
                p1, p2 = end - 1, end
            elif start > p1:
                # 需要添加一个新数字
                result += 1
                p1, p2 = p2, end
            # 否则当前区间已经被覆盖，无需添加
        
        return result

public class Solution {
    public int IntersectionSizeTwo(int[][] intervals) {
        Array.Sort(intervals, (a, b) => {
            if (a[1] != b[1]) return a[1].CompareTo(b[1]);
            return b[0].CompareTo(a[0]);
        });
        
        int p1 = -1, p2 = -1;
        int result = 0;
        
        foreach (var interval in intervals) {
            int start = interval[0], end = interval[1];
            
            if (start > p2) {
                // 需要添加两个新数字
                result += 2;
                p1 = end - 1;
                p2 = end;
            } else if (start > p1) {
                // 需要添加一个新数字
                result += 1;
                p1 = p2;
                p2 = end;
            }
            // 否则当前区间已经被覆盖，无需添加
        }
        
        return result;
    }
}

var intersectionSizeTwo = function(intervals) {
    intervals.sort((a, b) => {
        if (a[1] !== b[1]) return a[1] - b[1];
        return b[0] - a[0];
    });
    
    let p1 = -1, p2 = -1;
    let result = 0;
    
    for (const [start, end] of intervals) {
        if (start > p2) {
            // 需要添加两个新数字
            result += 2;
            p1 = end - 1;
            p2 = end;
        } else if (start > p1) {
            // 需要添加一个新数字
            result += 1;
            p1 = p2;
            p2 = end;
        }
        // 否则当前区间已经被覆盖，无需添加
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要消耗在排序操作，其中 n 为区间数量
空间复杂度O(1)只使用常数个额外变量存储状态