57.插入区间 python

题目

题目描述

给你一个 无重叠的 ，按照区间起始端点排序的区间列表 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 <= $10^4$
intervals[i].length == 2
0 <= starti <= endi <= $10^5$
intervals 根据 starti 按 升序 排列
newInterval.length == 2
0 <= start <= end <= $10^5$

题解

解题思路

为了在给定的无重叠且按起始端点排序的区间列表 intervals 中插入一个新的区间 newInterval，并保持区间列表的无重叠性和有序性，我们可以按照以下步骤来实现：

1. 遍历现有区间：我们遍历现有的区间列表 intervals，同时维护两个列表：一个是用于存储最终结果的 result 列表，另一个是用于累积需要合并的区间的 merge 列表。
2. 判断是否重叠：对于每个现有区间，我们需要检查它是否与 newInterval 重叠。如果它们之间有重叠，则将该区间加入到 merge 列表中，并更新 newInterval 的边界以包含所有这些重叠区间。
3. 处理非重叠区间：如果当前区间不与 newInterval 重叠并且位于 newInterval 之前，则直接将其添加到 result 列表中；如果位于 newInterval 之后，则先将 newInterval 添加到 result，然后将当前区间以及后续的所有区间都添加到 result。
4. 插入新区间：一旦完成了对所有可能与 newInterval 重叠的区间的处理，确保将 newInterval 插入到 result 列表中（如果还没有的话）。

python实现

下面是 Python 实现代码：

def insert(intervals, newInterval):
    if not intervals:
        return [newInterval]

    result = []
    i = 0
    n = len(intervals)

    # Add all intervals that end before newInterval starts
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

    # Merge all overlapping intervals to one considering newInterval
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1

    # Add the merged interval
    result.append(newInterval)

    # Add all intervals that start after newInterval ends
    while i < n:
        result.append(intervals[i])
        i += 1

    return result

代码解释

• 第一段循环：遍历所有结束于 newInterval 开始之前的区间，直接添加到结果列表中。
• 第二段循环：处理所有与 newInterval 重叠的区间，通过不断更新 newInterval 的边界来完成合并。
• 第三段循环：将所有开始于 newInterval 结束之后的区间添加到结果列表中。
• 插入 newInterval：确保在适当的位置插入合并后的 newInterval。

这种方法的时间复杂度主要取决于遍历 intervals 的操作，即 O(n)，其中 n 是 intervals 的长度。空间复杂度为 O(n)，因为最坏情况下我们可能会创建一个新的区间列表来保存结果。

提交结果