0757：设置交集大小至少为2（2378 分）

力扣第 757 题

题目

给你一个二维整数数组 intervals ，其中 intervals[i] = [starti, endi] 表示从 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 <= 108

分析

• 假设最优选择中的某个数 x 对应区间集合是 A
  • 将 x 变为 A 中最小的右端点，依然是最优选择
  • 假如该右端点已经有数 y 了，将 x 变为 y-1，依然是最优选择
• 于是得到贪心方法，将区间按右端点排序，若不够两个数，尽量选最右边的即可
• 遍历时，维护前面选的两个数即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
        res, pre = 0, [-1,-1]
        for s,e in sorted(intervals,key=lambda p:p[1]):
            if s>pre[1]:
                res += 2
                pre = [e-1,e]
            elif s>pre[0]:
                res += 1
                pre = [pre[1],e] if pre[1]<e else [e-1,e]
        return res

10 ms