[Leetcode] 57. Insert Interval

怼烎@ 2022-06-13 03:25 118阅读 0赞

**57. Insert Interval**  
Given a set of non-overlapping intervals, insert a new interval into the intervals(merge if necessary).  
You may assume that the intervals were initially sorted according to their start times.  
Example 1:  
Given intervals\*\*\[1,3\], \[6,9\],*\* insert and merge\[2,5\] in as\**\[1,5\], \[6, 9\]\*\*.  
Example 2:  
Given **\[1,2\], \[3,5\], \[6,7\],\[8,10\], \[12,16\]**, insert and merge **\[4,9\]** in as **\[1,2\], \[3,10\], \[12, 16\]**.  
This is because the new interval **\[4,9\]** overlaps with **\[3,5\], \[6,7\], \[8,10\]**.

**给定一系列不重叠的区间，并给定一个新区间，将该区间合并插入原来的不重叠区间。**  
**例如1：**   
**给定区间\[1,3\], \[6, 9\], 要求插入合并区间\[2, 5\], 可得到新的不重叠区间\[1, 5\], \[6, 9\].**  
**例如2 ：**  
**给定区间\[1, 2\], \[3, 5\], \[6, 7\], \[8, 10\], \[12, 16\], 要求插入合并区间\[4, 9\], 可得到新的不重叠区间\[1, 2\], \[3, 10\], \[12, 16\].**

**解题思路**  
这道题的困难程度是标记为Hard的题目。一个简单的解题思路是比较**要求插入合并的区间**与原始不重叠区间的大小。即将最大的小于**插入合并区间**的区间，和最小的大于**插入合并区间**的区间合并起来，就可以得到新的不重叠区间。  
代码实现如下：

/**
     * Definition for an interval.
     * struct Interval {
     *     int start;
     *     int end;
     *     Interval() : start(0), end(0) {}
     *     Interval(int s, int e) : start(s), end(e) {}
     * };
     */
    class Solution {
    public:
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
            vector<Interval>::iterator it = intervals.begin();
            while(it != intervals.end())
            {
                if(it->start > newInterval.end)
                {
                    intervals.insert(it, newInterval);
                    return intervals;
                }
                else if(it->end < newInterval.start)
                {
                    it++;
                    continue;
                }
                else
                {
                    newInterval.start = min(newInterval.start, it->start);
                    newInterval.end = max(newInterval.end, it->end);
                    it = intervals.erase(it);
                }
            }
            intervals.insert(intervals.end(), newInterval);
            return intervals;
        }
    };

但是该代码算法运行时间长，无法通过LeetCode的编译，会超时。

方法二：  
对以上算法进行优化，便可通过LeetCode的编译

/**
     * Definition for an interval.
     * struct Interval {
     *     int start;
     *     int end;
     *     Interval() : start(0), end(0) {}
     *     Interval(int s, int e) : start(s), end(e) {}
     * };
     */
    class Solution {
    public:
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
            int sz = intervals.size();
            vector<Interval> res;
    
            for(int i = 0; i < sz; i++)
            {
                if(intervals[i].end < newInterval.start)
                {
                    res.push_back(intervals[i]);
                }
                else if(intervals[i].start > newInterval.end)
                {
                    res.push_back(newInterval);
                    res.insert(res.end(),intervals.begin()+i,intervals.end());
                    return res;
                }
                else
                {
                    newInterval.start = min(newInterval.start, intervals[i].start);
                    newInterval.end = max(newInterval.end, intervals[i].end);
                }
            }
            res.push_back(newInterval);
            return res;
        }
    };