DEV Community
·
LeetCode 思考：插入区间
💡
原文英文，约800词，阅读约需3分钟。
📝
内容提要
给定一个非重叠区间数组和一个新区间，要求将新区间插入并合并重叠区间，保持数组按升序排列。时间复杂度为O(n)，空间复杂度为O(n)。
🎯
关键要点
- 给定一个非重叠区间数组和一个新区间，要求将新区间插入并合并重叠区间。
- 新区间的格式为 [start, end]，表示新区间的开始和结束。
- 插入后，区间数组仍需按升序排列，并且不应有重叠区间。
- 可以创建一个新的结果数组来存储结果，而不需要原地修改原数组。
- 通过遍历所有区间，判断新区间的位置并进行合并或插入。
- 如果新区间在当前区间之前，则直接将新区间添加到结果中。
- 如果新区间在当前区间之后，则将当前区间添加到结果中。
- 如果新区间与当前区间重叠，则需要合并这两个区间。
- 最后，将合并后的新区间添加到结果数组中并返回。
- 时间复杂度为 O(n)，空间复杂度为 O(n)。
➡️
