网站建设借鉴,大数据营销的核心,动漫设计网站,做网站新乡题目#xff1a; 给你一个 无重叠的 #xff0c;按照区间起始端点排序的区间列表。 在列表中插入一个新的区间#xff0c;你需要确保列表中的区间仍然有序且不重叠#xff08;如果有必要的话#xff0c;可以合并区间#xff09;。 来源#xff1a;力扣#xff08;LeetC… 题目 给你一个 无重叠的 按照区间起始端点排序的区间列表。 在列表中插入一个新的区间你需要确保列表中的区间仍然有序且不重叠如果有必要的话可以合并区间。 来源力扣LeetCode 链接力扣 示例 示例 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]] 解法 首先处理特殊情况如果intervals为空返回newInterval如果newInterval的右区间比intervals第1个区间的左区间小说明newInterval比intervals中所有区间小返回[newInterval] intervals同理如果newInterval的左区间比intervals第最后一个区间的右区间大返回intervals [newInterval]。剩下的情况进入算法结果存在result。 遍历intervals如果newInterval的左区间大当前区间的右区间说明没有交集添加当前区间到result。否则记录交集的左区间为当前区间和newInterval中小的左区间设为left。接着从当前区间开始遍历剩下intervals如果newInterval的右区间大于当前区间的右区间说明newInterval的范围可以覆盖当前区间所以可以跳过当前区间如果当前已经是最有一个区间设right为newInterval的右区间然后添加[left, right]到result返回result。如果newInterval的右区间小于等于当前区间的右区间说明和newInterval有交集的最大右区间已出现如果newInterval的右区间大于等于当前区间和左区间设right为newInterval和当前区间中大的右区间添加[left, right]到result然后把后面区间也加入result。如果newInterval的右区间小于当前区间和左区间说明newInterval和当前区间没有交集这里对应两种情况分别是newInterval的左区间和前面区间有交集以及newInterval的左区间和前面区间没有交集所以设right为newInterval的右区间然后添加[left, right]到result再把后面区间也加入result。 代码 class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) - List[List[int]]:if len(intervals) 0:return [newInterval]if newInterval[1] intervals[0][0]:return [newInterval] intervalsif newInterval[0] intervals[-1][1]:return intervals [newInterval]result []for index1, interval1 in enumerate(intervals):if newInterval[0] interval1[1]:left min(interval1[0], newInterval[0])for index2, interval2 in enumerate(intervals[index1:]):if newInterval[1] interval2[1]:if newInterval[1] interval2[0]:result.append([left, max(interval2[1], newInterval[1])])else:result.append([left, newInterval[1]])result.append(interval2)if index2 ! len(intervals[index1:]) - 1:result.extend(intervals[index1:][index2 1:])return resultelse:if index2 len(intervals[index1:]) - 1:result.append([left, newInterval[1]])return resultelse:result.append(interval1)
