目录
- 题目描述
- 解法
- 方法一:排序 + 区间合并
- 方法二:一次遍历
- 运行结果
- 方法一:排序 + 区间合并
- 方法二:一次遍历
题目描述
给你一个 无重叠的 ,按照区间起始端点排序的区间列表。
在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。
示例 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 <= 104
- intervals[i].length == 2
- 0 <= intervals[i][0] <= intervals[i][1] <= 105
- intervals 根据 intervals[i][0] 按 升序 排列
- newInterval.length == 2
- 0 <= newInterval[0] <= newInterval[1] <= 105
解法
方法一:排序 + 区间合并
我们可以先将新区间 newInterval 加入到区间列表 intervals 中,然后按照区间合并的常规方法进行合并。
时间复杂度 O(n×logn),空间复杂度 O(n)。其中 n 是区间的数量。
class Solution(object):def insert(self, intervals, newInterval):""":type intervals: List[List[int]]:type newInterval: List[int]:rtype: List[List[int]]"""def merge(intervals) :intervals.sort()ans = [intervals[0]]for s, e in intervals[1:]:if ans[-1][1] < s:ans.append([s, e])else:ans[-1][1] = max(ans[-1][1], e)return ansintervals.append(newInterval)return merge(intervals)
方法二:一次遍历
我们可以遍历区间列表 intervals,记当前区间为 interval,对于每个区间有三种情况:
- 当前区间在新区间的右侧,即 newInterval[1]<interval[0],此时如果新区间还没有被加入,那么将新区间加入到答案中,然后将当前区间加入到答案中。
- 当前区间在新区间的左侧,即 interval[1]<newInterval[0],此时将当前区间加入到答案中。
- 否则,说明当前区间与新区间有交集,我们取当前区间的左端点和新区间的左端点的最小值,以及当前区间的右端点和新区间的右端点的最大值,作为新区间的左右端点,然后继续遍历区间列表。
遍历结束,如果新区间还没有被加入,那么将新区间加入到答案中。
时间复杂度 O(n),其中 n 是区间的数量。忽略答案数组的空间消耗,空间复杂度 O(1)
class Solution(object):def insert(self, intervals, newInterval):""":type intervals: List[List[int]]:type newInterval: List[int]:rtype: List[List[int]]"""st, ed = newIntervalans = []insert = Falsefor s, e in intervals:if ed < s:if not insert:ans.append([st, ed])insert = Trueans.append([s, e])elif e < st:ans.append([s, e])else:st = min(st, s)ed = max(ed, e)if not insert:ans.append([st, ed])return ans