插入区间

标签: 数组

难度: Medium

给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

示例 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] 重叠。

提示：

  • 0 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 105
  • intervals 根据 starti 按 升序 排列
  • newInterval.length == 2
  • 0 <= start <= end <= 105

Submission

运行时间: 52 ms

内存: 16.3 MB

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        ans = []
        i = 0
        while i < len(intervals) and intervals[i][1] < newInterval[0]:
            ans.append(intervals[i])
            i += 1

        while i < len(intervals) and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(intervals[i][0], newInterval[0])
            newInterval[1] = max(intervals[i][1], newInterval[1])
            i += 1
        ans.append(newInterval)

        while i < len(intervals):
            ans.append(intervals[i])
            i += 1

        return ans

Explain

这个题解的思路是将新区间插入到原区间列表中的合适位置，同时合并所有重叠的区间。具体步骤如下： 1. 先将所有小于新区间左端点的区间添加到答案中 2. 然后将所有与新区间重叠的区间与新区间合并 3. 将合并后的新区间添加到答案中 4. 最后将剩余大于新区间右端点的区间添加到答案中

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        ans = []
        i = 0
        # 添加所有小于新区间左端点的区间到答案中
        while i < len(intervals) and intervals[i][1] < newInterval[0]:
            ans.append(intervals[i]) 
            i += 1
        
        # 合并所有与新区间重叠的区间
        while i < len(intervals) and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(intervals[i][0], newInterval[0])
            newInterval[1] = max(intervals[i][1], newInterval[1])
            i += 1
        # 将合并后的新区间添加到答案中
        ans.append(newInterval)
        
        # 添加剩余大于新区间右端点的区间到答案中
        while i < len(intervals):
            ans.append(intervals[i])
            i += 1
            
        return ans

Explore

在算法中，首先按照已排序的方式添加所有开始时间小于新区间的区间。然后处理可能与新区间重叠的区间，并与新区间合并。最后，添加所有剩余的、开始时间大于新区间的区间。这个过程从头到尾遵循原区间列表的顺序，因此可以确保整个列表在插入并合并后仍然是排序的。

两个区间被视为重叠的情况是，一个区间的开始时间小于或等于另一个区间的结束时间。具体来说，如果有两个区间[a, b]和[c, d]，当a <= d且b >= c时，这两个区间就重叠。这种重叠意味着它们至少有一个共同点或一个区间完全或部分地覆盖了另一个区间。

选择更新newInterval作为合并后的区间的主要优势在于减少了额外的内存使用和简化了逻辑。通过直接更新newInterval的起始和结束点，我们避免了创建新的区间列表，同时使代码更加简洁。此外，这种方法也减少了不必要的数组操作，可能会在某些情况下提高效率。

如果newInterval位于所有现有区间的最左端或最右端，算法的处理流程具体如下：1. 如果newInterval在最左端，循环检查小于新区间左端点的区间将直接跳过，因为没有这样的区间；然后直接将newInterval添加到结果列表，并继续添加剩余的区间。2. 如果newInterval在最右端，所有现有的区间都会被添加到结果列表中，因为它们的结束时间都小于newInterval的开始时间；之后再添加newInterval。在这两种情况下，算法自然适应新区间的位置，无需特别的分支逻辑。