Leetcode-57.插入区间

发表于 分类于 阅读次数：

题目描述

给出一个无重叠的 ，按照区间起始端点排序的区间列表。

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

示例 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] 重叠。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insert-interval
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1：暴力

考虑各种情况，完全模拟，代码很乱

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n=intervals.size();
        vector<vector<int>> res;
        if(n==0)
        {
            res.push_back(newInterval);
            return res;
        }
        int i,l=n;
        vector<int> pre;
        if(newInterval[1]<intervals[0][0])      //  放在头部，且不用合并
        {
            res.push_back(newInterval);
            l=0;
        }
        else
        {
            for(i=0;i<n;i++)
            {
                if(newInterval[0]<=intervals[i][1])           //找到插入位置
                {
                    if(newInterval[1]<=intervals[i][1]&&newInterval[0]>=intervals[i][0])    //插入位置被包含在一个区间，直接返回，不用合并
                    {   
                        return intervals;
                    }
                    if(newInterval[0]<=intervals[i][0])     //  判断新的插入位置，以哪个作为左位置，是新区间还是要插入的这个区间
                        pre.push_back(newInterval[0]);
                    else pre.push_back(intervals[i][0]);
                    int j=i;
                    for(;j<n;j++)                           
                    {
                        if(newInterval[1]<intervals[j][0])          //找到右位置应插入的位置
                        {

                            if(newInterval[1]<intervals[j-1][1])        //如果右位置比上一个区间的右位置小，把上一区间右位置记录
                                pre.push_back(intervals[j-1][1]);
                            else
                                pre.push_back(newInterval[1]);          //否则记录右位置
                            break;
                        }
                    }
                    l=j;
                    if(newInterval[1]>=intervals[n-1][1])               //如果插入区间右区间在最后，进行判断
                        pre.push_back(newInterval[1]);
                    else if(newInterval[1]>=intervals[n-1][0])
                        pre.push_back(intervals[n-1][1]);
                    res.push_back(pre);
                    break;
                }
                res.push_back(intervals[i]);
            }
        }
        while(l<n)
        {
            res.push_back(intervals[l]);
            l++;
        }
        if(newInterval[0]>intervals[n-1][1])                    //如果插入区间左区间在最后
            res.push_back(newInterval);
        return res;
    }
};

时间复杂度：O（N）

解法2：插入，合并

直接把新节点插入到最后，然后按照56题合并区间进行合并

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
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        intervals.push_back(newInterval);
        sort(intervals.begin(),intervals.end());
        vector<vector<int>> res;
        vector<int> pre;
        int i,n=intervals.size();
        if(n==0)
            return res;
        pre.push_back(intervals[0][0]);
        pre.push_back(intervals[0][1]);
        for(i=0;i<n;i++)
        {
            if(intervals[i][0]<=pre[1])
            {
                if(pre[1]>=intervals[i][1])
                    continue;
                else
                {
                    pre[1]=intervals[i][1];
                }
            }
            else
            {
                res.push_back(pre);
                pre.clear();
                pre.push_back(intervals[i][0]);
                pre.push_back(intervals[i][1]);
            }
        }
        if(!pre.empty())
            res.push_back(pre);
        return res;
    }
};

时间复杂度：O（NlogN）

解法3：找左右重合区域

1.先找到左边重合区域，即若newInterval[0] > intervals[i][1]就将intervals加入res。

2.找右边重合区域，若newInterval[1] >= intervals[i][0]就与temp找到区间范围最大的

3.最后将后面未遍历的intervals添加进res

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
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        intervals.push_back(newInterval);
        sort(intervals.begin(),intervals.end());
        vector<vector<int>> res;
        vector<int> pre;
        int i,n=intervals.size();
        if(n==0)
            return res;
        pre.push_back(intervals[0][0]);
        pre.push_back(intervals[0][1]);
        for(i=0;i<n;i++)
        {
            if(intervals[i][0]<=pre[1])
            {
                if(pre[1]>=intervals[i][1])
                    continue;
                else
                {
                    pre[1]=intervals[i][1];
                }
            }
            else
            {
                res.push_back(pre);
                pre.clear();
                pre.push_back(intervals[i][0]);
                pre.push_back(intervals[i][1]);
            }
        }
        if(!pre.empty())
            res.push_back(pre);
        return res;
    }
};