LeetCode50天刷题计划（Day 31— 插入区间（9.00-11.20）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

今天起太早了 神志不清真的是

一、题目

插入区间

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例

示例 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
1
2
3
4
5
6

二、思路

1.混乱

二维数组转一位数组的方法：

这个方法双百分之五，我真的不愿再提，大概就是遍历数组得到比newInterval[0]小的第一个数和比newInterval[1]大的第一个数，然后确定其下标，根据不同情况在原数组中切片修改。写了40行太麻烦了真的会谢。

2.重新理一遍思路

①首先，对于区间 S1 =[ l1,r1 ] 和 S2 = [l2, r2]，如果它们之间没有交集，说明要么 S1在 S2的左侧（ r1 < l2），要么 S1在 S2的右侧（l1 > r2），如果 二者均不满足，说明 S1和 S2必定有交集，它们的交集即为：

[max(l1, l2), min(r1, r2)]
1

并集即为：

[min(l1, l2), max(r1, r2)]
1

②因此，选择对intervals进行遍历，并提前准备一个结果数组，遍历中会出现以下三种情况：
若当前区间与newInterval不重叠且在其左边，直接加入结果中；
若当前区间与newInterval重叠，将其合并到newinterval中（此后合并的区间应是连续的）；
当遇到第一个与newInterval不重叠且在其右边的区间，将合并后的newinterval加入结果中，并将剩余区间全部加入结果中；

③也还是有一些细节需要注意，比如如果重叠的区间一直到最后一个，那么就无法遇到第一个与newInterval不重叠且在其右边的区间，而是直接跳出了循环。因此不能将“newinterval加入结果，并将剩余区间全部加入结果中”这一步放在这个判断条件后，而应该放在for循环外面。比如：

[[1,5]]
[2,3]
1
2

或

[]
[5,7]
1
2

三、代码

1.难看

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if(intervals==[]):
            return [newInterval]
        if(newInterval[0]>intervals[-1][1]):
            intervals.append(newInterval)
            return intervals
        if(newInterval[1]<intervals[0][0]):
            intervals.insert(0,newInterval)
            return intervals
        before,after=[],[] #分别指向比newInterval[0]小的第一个数和比newInterval[1]大的第一个数
        l=sum(intervals,[]) #转为一维
        for i in range(len(l)):
            if(l[i]==newInterval[0] and i%2==1):
                before=[i//2,0]
            elif(i<len(l)-1 and l[i]<=newInterval[0] and l[i+1]>newInterval[0]): #比newInterval[0]小的第一个数
                before=[i//2,i%2] #在intervals中的下标
            if(l[i]==newInterval[1] and i%2==0):
                after=[i//2,1]
                break
            elif(l[i]>=newInterval[1] and l[i-1]<newInterval[1]): #比newInterval[1]大的第一个数
                after=[i//2,i%2]
                break
        #一些特殊情况
        if(before==[] and after==[]):
            return [newInterval]
        elif(before==[]):
            before=[-1,1]
        elif(after==[]):
            after=[len(intervals),0]

        #print(before,after)
        #before和after位置的四种情况，对原数组进行切片修改
        if(before[1]==0 and after[1]==1):
            intervals[before[0]:after[0]+1] = [[intervals[before[0]][0],intervals[after[0]][1]]]
        elif(before[1]==0 and after[1]==0):
            intervals[before[0]:after[0]] = [[intervals[before[0]][0],newInterval[1]]]
        elif(before[1]==1 and after[1]==1):
            intervals[before[0]+1:after[0]+1] = [[newInterval[0],intervals[after[0]][1]]]
        else:
            intervals[before[0]+1:after[0]] = [[newInterval[0],newInterval[1]]]
        
        #返回
        return intervals
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

2.好一点

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        flag=0 #记录
        relist=[] #返回值
        for i in range(len(intervals)):
            if(intervals[i][1]<newInterval[0]): #在左边
                relist.append(intervals[i])
                flag+=1
            elif(newInterval[1]<intervals[i][0]): #在右边
                break
            else: #重叠，求并集
                newInterval[0]=min(intervals[i][0],newInterval[0])
                newInterval[1]=max(intervals[i][1],newInterval[1])
                flag+=1 #下一个要合的
        relist.append(newInterval) 
        relist.extend(intervals[flag:])
        return relist
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17