LeetCode-57-插入区间
题目
给你一个 无重叠的
,按照区间起始端点排序的区间列表 intervals
,其中
intervals[i] = [starti, endi]
表示第 i
个区间的开始和结束,并且 intervals
按照 starti
升序排列。同样给定一个区间 newInterval = [start, end]
表示另一个区间的开始和结束。
在 intervals
中插入区间 newInterval
,使得
intervals
依然按照 starti
升序排列,且区间之间不重叠(如果有必要的话,可以合并区间)。
返回插入之后的 intervals
。
注意 你不需要原地修改
intervals
。你可以创建一个新数组然后返回它。
示例 1:
1 |
|
示例 2:
1 |
|
提示:
0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 105
intervals
根据starti
按 升序 排列newInterval.length == 2
0 <= start <= end <= 105
题解
这一题其实不算很难,需要静下心来好好分析一下:
一次遍历intervals
,当前区间如果为interval
,对于每个区间有三种情况:
- 当前区间在新区间的右侧,也就是
newInterval[1] < interval[0]
,这时如果新区间没有被加入,需要加入新区间然后再加入当前区间; - 当前区间在新区间的左侧,即
newInterval[1] < interval[0]
,这个时候把当前区间加入到答案里; - 否则,说明新区间和当前区间有交集,我们取当前区间的左端点和新区间左端点的最小值,然后取当前区间的右端点和新区间右端点的最大值,作为新区间的断电,继续遍历。
- 当遍历完成了,新区间还未被加入,把新区间加入到答案里。
1 |
|
LeetCode-57-插入区间
https://excelius.xyz/leetcode-57-插入区间/