七十二、区间合并，插入求交集，删除求覆盖元素

「@Author：Runsen」

❝

编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。「---- Runsen」

❞

我从来不是一个呆在舒适区间的人，高中毕业，大学往死了干了三年，毕竟还是要靠实力说话啊，努力、自制、对照下，喜欢呆在舒适区间里人，没紧迫感、没压力、不思进取、“人无远虑必有近忧”的人。这么一想，我好像也有点强逼自己变得更强。

来吧，我还是那个少年。

Leetcode 56. 合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:

输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

此题，我大二应该做过，可惜那是以前的我。现在的我好像还可以A掉。

原理就是：新的区间左边的数字为原第一个区间左边的数字，新区间右边的数字为 原第一个区间右边数字和原第二个区间右边数字的最大值。

此题的难点就是判断哪些区间重叠了，以及如何进行合并。重叠只有两种情况，一个区间是另外一个区间的子集，或者两个区间相邻（有部分重叠）。

因此需要判断第一个区间最后的元素和第二个区间开头和最后的元素的大小关系。

如果第二个区间开头的元素小于第一个区间最后的元素，返回第一个区间开头的元素和max(第一个区间最后的元素,第二个区间最后的元素)。

❝

「注意：前提是区间第一个值按照顺序排列」

❞

对于出现重叠的情况，比如[0, 4], [3, 5]。由于3 < 4且4 < 5，因此得到新区间为[0, 5]。

对于一个区间是另外一个区间的子集的情况，比如[0, 6], [3, 5]。由于3 < 6且6 > 5，因此得到新区间为[0, 6]。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals: return []
        # 对区间进行排序
        intervals.sort(key=lambda x:x[0])
        res = [intervals[0]]
        for i in range(1,len(intervals)):
            if intervals[i][0] <= res[-1][1]:
                res[-1] = [res[-1][0], max(intervals[i][1], res[-1][1])]
            else:
                res.append(intervals[i])
        return res

Leetcode 57.插入区间

Leetcode 57.插入区间和 Leetcode 56. 合并区间完全一样，变汤不变料。

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        # 其原理和合并区间一样
        intervals.append(newInterval)
        intervals.sort()
        res = [intervals[0]]
        for i in range(1,len(intervals)):
            # 判断
            if res[-1][1] >= intervals[i][0]:
                res[-1] = [res[-1][0],max(res[-1][1],intervals[i][1])]
            else:
                res.append(intervals[i])
        return res

Leetcode 986. 区间列表的交集

给定两个由一些闭区间组成的列表，每个区间列表都是成对不相交的，并且已经排序。

返回这两个区间列表的交集。

❝

形式上，闭区间 [a,b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b。两个闭区间的交集是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4]的交集为 [2, 3]。

❞

现有如下两个区间求交集：[a1,a2],[b1,b2]

如果a2 < b1或者a1 > b2，那么没有交集。比如[1,2],[3,4]，[3,4]，[1,2]

如果a2>=b1 && a1 <= b2，可以发现，有交集区间：[max(a1, b1), min(a2, b2)]

比如，[1, 3] 和 [2, 4]，有交集区间：[max(1, 2), min(3, 4)]

用两个指针，分别扫描 A、B 数组，根据子区间的左右端，求出一个交集区间

指针移动，直至指针越界，得到由交集区间组成的数组。

关键就是最后一步，指针i和j什么时候应该前进呢？只要判断两个数组右指针的大小可以 了。

class Solution:
    def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
        i, j = 0, 0 # 双指针
        res = []
        while i < len(A) and j < len(B):
            a1, a2 = A[i][0], A[i][1]
            b1, b2 = B[j][0], B[j][1]
            # 两个区间存在交集
            if b2 >= a1 and a2 >= b1:
                # 计算出交集，加入 res
                res.append([max(a1, b1), min(a2, b2)])
            # 指针前进
            if b2 < a2: 
                j += 1
            else:       
                i += 1
        return res

Leetcode 1288. 删除被覆盖区间

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。

只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。

在完成所有删除操作后，请你返回列表中剩余区间的数目。

输入：intervals = [[1,4],[3,6],[2,8]]
输出：2
解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。

循环数字每行，默认计数为0。然后依次判断是否被包含。没有被包含则计数加1，否则循环下一个。最后返回计数

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        # 排序
        intervals.sort(key = lambda x: (x[0], -x[1]))
        count = 0
        prev_end = 0
        for _, end in intervals:
            if end > prev_end:
                count += 1    
                prev_end = end
        return count  

❝

本文已收录 GitHub，传送门~^[1] ，里面更有大厂面试完整考点，欢迎 Star。

❞

Reference