leetcode-57

57. 插入区间

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例

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

输入：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] 重叠。

输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]

解法

解法一

仿照56题的思路，将新的元素添加到列表中，然后排序，再进行合并区间。

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: 
        intervals.append(newInterval)
        intervals.sort(key=lambda x: x[0])

        res = []

        for inter in intervals:

            if not res or res[-1][1] < inter[0]:
                res.append(inter)
            else:
                res[-1][1] = max(res[-1][1],inter[1])

        return res

解法二：官方题解

对于区间$S_1=[l1,r1]$和$S_2=[l2,r2]$，如果它们之间没有重叠（没有交集），说明要么$S_1$在$S_2$的左侧，此时有$r_1<l_2$；要么$S_1$在$S_2$的右侧，此时有$l_1>r_2$。

如果$r_1<l_2$和$l_1>r_2$二者均不满足，说明$S_1$和$S_2$必定有交集，它们的交集为：
$$
[ \max ( l 1 , l 2 ) , \min ( r 1 , r 2 ) ]
$$
并集即为
$$
\left[ \min \left( l _ { 1 } , l _ { 2 } \right) , \max ( r 1 , r 2 ) \right]
$$
在给定的区间集合$\mathcal{X}$互不重叠的前提下，当我们需要插入一个新的区间$S=[left,right]$时，我们只需要：

• 找出所有与区间 $S$ 重叠的区间集合$\mathcal{X}’$
• 将$\mathcal{X}’$中的所有区间连带上区间$S$合并成一个大区间
• 最终的答案即为不与$\mathcal{X}’$重叠的区间以及合并后的大区间。

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        left, right = newInterval
        placed = False
        ans = list()
        for li, ri in intervals:
            if li > right:
                # 在插入区间的右侧且无交集
                if not placed:
                    ans.append([left, right])
                    placed = True
                ans.append([li, ri])
            elif ri < left:
                # 在插入区间的左侧且无交集
                ans.append([li, ri])
            else:
                # 与插入区间有交集，计算它们的并集
                left = min(left, li)
                right = max(right, ri)
        
        if not placed:
            ans.append([left, right])
        return ans