DEV Community
·
LeetCode 思考：插入区间
💡
原文英文，约800词，阅读约需3分钟。
📝
内容提要
给定一个非重叠区间数组和一个新区间，要求将新区间插入并合并重叠区间，保持数组按升序排列。时间复杂度为O(n)，空间复杂度为O(n)。
🎯
关键要点
- 给定一个非重叠区间数组和一个新区间，要求将新区间插入并合并重叠区间。
- 新区间的格式为 [start, end]，表示新区间的开始和结束。
- 插入后，区间数组仍需按升序排列，并且不应有重叠区间。
- 可以创建一个新的结果数组来存储结果，而不需要原地修改原数组。
- 通过遍历所有区间，判断新区间的位置并进行合并或插入。
- 如果新区间在当前区间之前，则直接将新区间添加到结果中。
- 如果新区间在当前区间之后，则将当前区间添加到结果中。
- 如果新区间与当前区间重叠，则需要合并这两个区间。
- 最后，将合并后的新区间添加到结果数组中并返回。
- 时间复杂度为 O(n)，空间复杂度为 O(n)。
❓
延伸问答
如何将新区间插入到非重叠区间数组中？
通过遍历所有区间，判断新区间的位置并进行合并或插入，确保数组按升序排列且无重叠。
新区间的格式是什么？
新区间的格式为 [start, end]，表示新区间的开始和结束。
插入新区间后，如何确保区间数组仍然按升序排列？
在插入新区间时，需判断新区间与当前区间的关系，适时合并或插入，保持数组的升序。
合并重叠区间的条件是什么？
两个区间重叠的条件是一个区间的开始大于另一个区间的结束，或者结束小于开始时都不成立。
插入新区间的时间和空间复杂度是多少？
时间复杂度为 O(n)，空间复杂度也为 O(n)。
如何处理新区间与现有区间重叠的情况？
如果新区间与当前区间重叠，则需要合并这两个区间，使用最小值和最大值更新新区间。
➡️
