【题目】
给你一个 无重叠的 ， 按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 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] 重叠。
示例 3：
输入： intervals = [], newInterval = [5,7]
输出： [[5,7]]
示例 4：
输入： intervals = [[1,5]], newInterval = [2,3]
输出： [[1,5]]
示例 5：
输入： intervals = [[1,5]], newInterval = [2,7]
输出： [[1,7]]
提示：
- 0 <= intervals.length <=
- intervals[i].length == 2
- 0 <= intervals[i][0] <= intervals[i][1] <=
- intervals
根据intervals[i][0] 按 升序 排列 - newInterval.length == 2
- 0 <= newInterval[0] <= newInterval[1] <=
【题目解析】
方法解析
初始化：创建一个空列表
merged，用于存放最终合并后的区间。-
遍历区间列表：
-
不重叠且在新区间左侧：如果当前区间的结束位置小于新区间的起始位置，将当前区间添加到
merged。 - 重叠：如果当前区间与新区间重叠（当前区间的起始位置小于等于新区间的结束位置，并且当前区间的结束位置大于等于新区间的起始位置），则将新区间更新为这两个区间的并集。
-
不重叠且在新区间右侧：如果遇到的区间起始位置大于新区间的结束位置，说明新区间的位置已确定，将新区间添加到
merged，并将剩余区间全部添加到merged。
-
不重叠且在新区间左侧：如果当前区间的结束位置小于新区间的起始位置，将当前区间添加到
添加新区间：如果遍历结束后新区间还没有被添加到
merged，则将其添加到最后。
def insert(intervals, newInterval):
merged = []
i, n = 0, len(intervals)
# 遍历并添加所有在新区间左侧且不重叠的区间
while i < n and intervals[i][1] < newInterval[0]:
merged.append(intervals[I])
i += 1
# 合并所有与新区间重叠的区间
while i < n and intervals[i][0] <= newInterval[1]:
newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]
i += 1
merged.append(newInterval)
# 添加所有在新区间右侧且不重叠的区间
while i < n:
merged.append(intervals[I])
i += 1
return merged
执行效率
image.png
【总结】
适用问题类型
- 区间操作问题：这类问题包括但不限于区间合并、区间插入、区间交集等，特别是那些涉及有序区间集合的问题。
解决算法：排序加贪心算法
算法描述：首先根据区间起始点进行排序（如果输入已经有序，则可跳过此步骤），然后通过一次遍历，贪心地选择合并或插入区间的方式来处理重叠或相邻的区间。
-
关键步骤：
- 遍历区间列表，寻找插入点。
- 根据新区间与当前区间的关系（不重叠、完全重叠、部分重叠）来决定是直接插入新区间、合并区间，还是保留现有区间。
- 更新结果集合。
算法特点
- 高效性：通过一次遍历完成区间的插入和合并，避免了不必要的重复比较和计算。
- 简洁性：算法逻辑清晰，实现简洁，易于理解和维护。
- 通用性：适用于多种区间操作问题，具有良好的可扩展性。
时间复杂度与空间复杂度
-
时间复杂度：
O(N log N)，主要时间开销在于排序步骤。如果区间列表已经有序，则时间复杂度降为O(N)，其中N是区间列表的长度。 -
空间复杂度：
O(N)，需要额外空间来存储合并后的区间列表。
实践意义
- 广泛应用：这种方法不仅适用于编程竞赛中的算法题目，也可用于实际开发中涉及时间段、资源分配等区间操作的场景。
- 算法思维培养：通过学习和实践这种算法，可以培养解决问题时寻找局部最优解以推导全局最优解的思维方式。
- 性能优化：理解和掌握贪心算法及其在区间操作问题中的应用，有助于在面对实际问题时设计出更高效、更稳定的解决方案。
总之，"插入区间"问题的解法提供了一种有效处理区间集合的方法，不仅解决了特定的问题场景，还拓展了我们对贪心算法在实际应用中的理解和使用。
