题目

一个整数区间 [a, b] ( a < b ) 代表着从 a 到 b 的所有连续整数，包括 a 和 b。

给你一组整数区间intervals，请找到一个最小的集合 S，使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。

输出这个最小集合S的大小。

示例

示例 1:

输入: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]

输出: 3

解释: 考虑集合 S ={2, 3, 4}. S与intervals中的四个区间都有至少2个相交的元素。 且这是S最小的情况，故我们输出3。

示例 2:

输入: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]

输出: 5

解释: 最小的集合S ={1, 2, 3, 4, 5}.

注意:

intervals 的长度范围为[1, 3000]。

intervals[i] 长度为 2，分别代表左、右边界。

intervals[i][j] 的值是 [0, 10^8]范围内的整数。

思路

1.先将intervals中的数组排序，规则为：首先按照右边界从小到大排序，右边界相同的按照左边界由大到小排序（目的是先处理数组长度较短的）

2.遍历排序后的intervals，并维持一个集合temp。判断intervals中的每一个集合temp的交叉情况

①无交叉，需要在temp中添加两个元素，这两个元素分别为右边界和右边界前一个元素

②有一个交叉，在temp中添加一个元素，为右边界元素

③有两个交叉，直接跳过

题解

class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:   
        # 排序
        intervals.sort(key = lambda x:(x[1],-x[0]))
        # 维持的集合
        temp = [-1,-1]
        # 遍历intervals
        for x in intervals:
            # 有两个交叉或以上的元素
            if x[0] <= temp[-2]:
                continue
            # 下面为一个交叉和零个交叉的情况
            # 1、零个交叉，加入右边界前一个元素及下方右边界
            if x[0] > temp[-1]:
                temp.append(x[1]-1)
            # 2、一个交叉只需加入右边界
            temp.append(x[1])
        return len(temp) - 2