1.题目基本信息

1.1.题目描述

给你一个二维整数数组 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.2.题目地址

https://leetcode.cn/problems/set-intersection-size-at-least-two/description/

2.解题方法

2.1.解题思路

贪心

2.2.解题步骤

第一步，将intervals按第二个元素升序，第一个元素降序进行排列

第二步，构建维护变量。a,b分别维护交集中的次大值和最大值

第三步，依次遍历排序后的intervals，在a,b的状态下贪心地尽量多地匹配区间，并做出最优转移，贪心地转移到e是为了下一个子问题中该点能出现在尽量多的后续区间中；分为s>b、a<s<=b、s<=a三种情况进行讨论，分别对应无交集、1个交集、2个交集

3.解题代码

python3代码

class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
        # 思路：贪心
        # 第一步，将intervals按第二个元素升序，第一个元素降序进行排列
        intervals.sort(key = lambda x:(x[1], -x[0]))
        # 第二步，构建维护变量。a,b分别维护交集中的次大值和最大值
        a, b = -1, -1
        result = 0
        # 第三步，依次遍历排序后的intervals，在a,b的状态下贪心地尽量多地匹配区间，并做出最优转移，贪心地转移到e是为了下一个子问题中该点能出现在尽量多的后续区间中；分为s>b、a<s<=b、s<=a三种情况进行讨论，分别对应无交集、1个交集、2个交集
        for s, e in intervals:
            if s > b:
                b = e
                a = b - 1
                result += 2
            elif s > a:
                a = b
                b = e
                result += 1
        return result

4.执行结果