【leetcode】-区间问题-57. Insert Interval

题目链接

https://leetcode.com/problems/insert-interval/

题目描述

给定一个按照区间起始端点排序的区间列表,列表里的区间不互相重叠。在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。题目中认为[4,8]和[8,10]这类边界接触的区间是重叠的,需要合并。

示例

输入: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]重叠。

解题思路

由于给定的区间列表已经按照起始端点排序好了,新区间插入进来,有可能和已有区间重叠,这时候就需要合并。哪些区间是需要合并的区间呢?这就需要我们通过遍历来判断。

对于区间问题,画图更直观一些,下面结合一个例子来了解步骤。举例intervals = [[0,1],[2,5],[6,9],[10,13]],待插入的区间为[4,7],维护一个result数组来存新的区间集合。

【leetcode】-区间问题-57. Insert Interval

我们可以看出,区间列表可以被划分为三个部分:左边和新区间不重叠的部分,中间和新区间产生重叠的部分(可能为空),右边和新区间不重叠的部分(可能为空)。因此在遍历过程中我们对会依次处理这三个部分。

【leetcode】-区间问题-57. Insert Interval

(1)找第一个重叠的区间(遍历左边和新区间不重叠的部分

从前往后遍历区间列表,如果区间intervals[i].end<newInterval.start,说明区间intervals[i]和newInterval一定是无重叠的,这部分直接加入result。

如果遍历到某个区间出现intervals[index].end>=newInterval.start,那么intervals[index]一定是和newInterval有重叠的,并且在intervals[index]后面可能还有区间和newInterval重叠。
在例子中,我们可以看到[0,1]和[4,7]不重叠。由于5>4,因此[2,5]是和[4,7]重叠的第一个区间。

(2)从intervals[index]开始继续找都有哪些区间和新区间重叠,找到并合并(遍历中间和新区间产生重叠的部分

从找到第一个和newInterval重叠的区间开始,判断重叠的条件就变了。如果intervals[i].start<=newInterval.end,那么有intervals[i]和newInterval重叠。很显然[2,5]是和[4,7]满足这个条件。发现重叠就合并,将[2,5]和[4,7]合并为[2,7](合并区间的start取两个区间start的较小值,合并区间的end取两个区间end的较大值),并将[2,7]视为要插入的新区间,需要保证后面的区间和[2,7]不重叠。

【leetcode】-区间问题-57. Insert Interval

 

继续遍历,得到[6,9]和[2,7]重叠(6<7),进一步将[6,9]和[2,7]合并为[2,9],并将[2,9]视为要插入的新区间。

【leetcode】-区间问题-57. Insert Interval

继续判断发现[2,9]和[10,13]不重叠(10 > 9),那么[10,13]后面即使继续有区间,也不会和[2,9]有重叠了。因此将合并得到的新区间[2,9]加入result中,并将后面的不重叠区间依次加入result数组。【leetcode】-区间问题-57. Insert Interval

Python实现

从分析中得到,代码中应该有三个while循环,第一个循环用来找区间列表中第一个和新区间产生重叠的区间,并将前面的无重叠区间加入result。第二个循环用来找全和新区间产生重叠的区间并且合并。第三个循环用来将后面无重叠的区间加入result。

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result = []
        i = 0
        n = len(intervals)
        while(i<n and intervals[i][1] < newInterval[0]): #将前面和newInterval不重合的部分依次加入result中
            result.append(intervals[i])
            i += 1
        #跳出上一个while循环时候i的值为第一个和newInterval有重合的区间索引,但也有可能i = n(表示区间列表中的所有区间都不和newInterval重合),因此下面的while条件句中也不要忘了i<n
        while(i<n and intervals[i][0] <= newInterval[1]): 
            newInterval[0] = min(intervals[i][0],newInterval[0])
            newInterval[1] = max(intervals[i][1],newInterval[1])
            i += 1
        #将合并好的区间加入result
        result.append(newInterval)
        #跳出上一个while循环时,i的值为后面部分第一个不和newInterval产生重合的区间,逐个加入
        while(i<n):
            result.append(intervals[i])
            i += 1
        return result
        

这道题还可以先将新的区间加入intervals,然后直接对intervals合并。这就和【leetcode-Python】-区间问题-56. Merge Intervals题目一样了。代码如下:


 

上一篇:利用setTimeout实现setInterval


下一篇:8位12指令硬布线CPU设计