设置交集大小至少为2

难度: Hard

给你一个二维整数数组 intervals ，其中 intervals[i] = [start_i, end_i] 表示从 start_i 到 end_i 的所有整数，包括 start_i 和 end_i 。

包含集合 是一个名为 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 <= start_i < end_i <= 10⁸

Submission

运行时间: 33 ms

内存: 17.2 MB

"""
按结束为止排序，当两个结束位置相同时，起始位置大的排前面先处理，这也符合我们先处理小区间的原则
It is actually much simpler to understand, since once you sort intervals by end-point, 
you just left with 3 cases to consider:
1. Next interval does not overlap，这时候我们就需要从当前区间中取出两个数字加入集合S，取哪两个数呢？
为了尽可能少使用数字，我们取当前区间中的最大两个数字，因为我们区间位置不断变大，
所以取大的数字有更高的概率能和后面的区间有交集。
2. Intervals overlap 二者有一个数字的交集，那么这个交集数字一定是区间的起始位置，
那么我们需要从当前区间中再取一个数字加入集合S，根据上面的分析，我们取最大的那个数，即区间的结束位置
3. Next interval contains previous one, 二者有两个及两个以上数字的交集，那么不用做任何处理.
具体算法如下：用个数组v来表示集合S，先给区间排序，然后遍历每个区间，
case 3: 如果区间的起始位置小于等于数组的倒数第二个数字，说明此时已经有两个相同的数字了，直接跳过当前区间。
case 1: 否则如果区间的起始位置大于数组的最后一个位置，说明二者没有任何交集，
我们此时把区间的最小和倒数第二小的数字加入数组v中。
"""
# class Solution:
#     def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
#         # need to sort increasingly by end time and decreasingly by start time.
#         # why decreasingly by start time? run an example: [[16,18],[11,18],[18,20],[10,11]]
#         # 我们总是优先处理小区间，如果先处理大空间的话会造成混乱
#         intervals.sort(key = lambda x: (x[1], -x[0]))      
#         v = []
#         for start, end in intervals:
#             if not v or v[-1] < start:  # case 1: 没有任何交集
#                 v.append(end - 1)       # 就需要加入两个数来形成长度至少为2的intersection
#                 v.append(end)           # greedily, v是一小段一小段不连续的长度为二的区间[1,2,  5,6]
                
#             elif start <= v[-2]:        # case 3: 已经有两个相同的数字的交集了  
#                 continue                # 就不需要加入任何数字了，因为已经有至少为2的intersection了
                
#             else:                       # case 2: 有一个数字的交集
#                 v.append(end)           # 就只需要加入一个数字来形成长度至少为2的intersection
                
#         return len(v)


class Solution:
    def intersectionSizeTwo(self, intervals):
        # 根据区间的结束点升序排序；如果结束点相同，则根据开始点降序排序
        intervals.sort(key=lambda x: (x[1], -x[0]))

        # 初始化一个列表，用于记录选择的点，开始时添加一个哨兵值-1以处理边界情况
        points = [-1]

        # # 贪心思路：每次都选最右边的点
        count = 0
        for interval in intervals:
            # 遍历每个区间
            if interval[0] > points[-1]:
                # 如果当前区间的开始点大于points中最后一个点，
                # 表明没有点能覆盖当前区间，需要添加两个新点
                # 添加当前区间的最后两个点确保至少有两个点可以覆盖该区间
                points.append(interval[1] - 1)
                points.append(interval[1])
                count += 2  # 更新计数
            elif interval[0] > points[-2]:
                # 如果当前区间的开始点大于points中倒数第二个点，
                # 但小于或等于最后一个点，说明只有一个点覆盖当前区间
                # 此时只需要添加当前区间的最后一个点
                points.append(interval[1])
                count += 1  # 更新计数

        # 返回满足条件的点的总数，即至少有两个点覆盖每个区间
        return count

Explain

本题采用贪心算法，按区间结束位置排序，当结束位置相同时按起始位置降序排序。遍历区间，根据当前选择的点和区间的起始位置，分为三种情况：1.当前区间与已选点无交集，需要添加该区间的最后两个点；2.当前区间与已选点有一个交集，只需添加该区间的最后一个点；3.当前区间与已选点有至少两个交集，不需要添加任何点。最终返回选择的点的总数。

时间复杂度: O(nlogn)

空间复杂度: O(n)

class Solution:
    def intersectionSizeTwo(self, intervals):
        # 根据区间的结束点升序排序；如果结束点相同，则根据开始点降序排序
        intervals.sort(key=lambda x: (x[1], -x[0]))

        # 初始化一个列表，用于记录选择的点，开始时添加一个哨兵值-1以处理边界情况
        points = [-1]

        # 贪心思路：每次都选最右边的点
        count = 0
        for interval in intervals:
            # 遍历每个区间
            if interval[0] > points[-1]:
                # 如果当前区间的开始点大于points中最后一个点，
                # 表明没有点能覆盖当前区间，需要添加两个新点
                # 添加当前区间的最后两个点确保至少有两个点可以覆盖该区间
                points.append(interval[1] - 1)
                points.append(interval[1])
                count += 2  # 更新计数
            elif interval[0] > points[-2]:
                # 如果当前区间的开始点大于points中倒数第二个点，
                # 但小于或等于最后一个点，说明只有一个点覆盖当前区间
                # 此时只需要添加当前区间的最后一个点
                points.append(interval[1])
                count += 1  # 更新计数

        # 返回满足条件的点的总数，即至少有两个点覆盖每个区间
        return count

Explore

这种排序策略主要是为了简化后续的贪心选择过程。首先，根据区间的结束位置升序排序，确保在处理当前区间时，之前的区间都已被处理，可以有效地使用已选择的点来尽可能覆盖多个区间。其次，当多个区间有相同的结束位置时，按照起始位置降序排序使得起始位置较晚的区间先被处理，这样可以更容易地使用已经选择的点来覆盖这些区间，减少额外点的添加。这种排序方法有助于我们从左到右处理区间，并尽可能利用已选择的点，避免不必要的重叠和点的浪费。

在算法执行过程中，通过对每个遍历到的区间，基于已选择点的情况（存在于列表`points`中），进行判断和处理。具体逻辑如下：1. 如果区间的起始点大于`points`中最后一个点，说明当前区间与已选点无交集，此时需添加该区间的最后两个点，即`interval[1]-1`和`interval[1]`，确保此区间被至少两个点覆盖。2. 如果区间的起始点大于`points`中倒数第二个点但小于或等于最后一个点，说明当前区间与已选点正好有一个交集，此时只需添加`interval[1]`，以确保区间被两个点覆盖。这样的处理确保了每个区间至少被两个点覆盖。

如果区间的开始点恰好等于`points`中最后一个点，这意味着当前区间与已选的点集有恰好一个交集点（即`points`中最后一个点）。在这种情况下，根据贪心算法的逻辑，我们仅需要再添加一个点，即区间的结束点`interval[1]`，以满足题目要求的至少有两个点覆盖每个区间的条件。这样不仅确保了覆盖，还保持了选择点数的最小化。