LeetCode 57.Insert Interval (插入区间)

矫情吗；* 2022-05-10 03:56 190阅读 0赞

题目描述：

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

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

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

AC C++ Solution:

首先，将所有间隔放在插入间隔的左侧。  
其次，合并与插入的间隔相交的所有间隔。  
最后，将所有间隔放在插入间隔的右侧。

/**
     * 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> res;
            int index = 0;
            while(index < intervals.size() && intervals[index].end < newInterval.start){
                res.push_back(intervals[index++]);
            }
            while(index < intervals.size() && intervals[index].start <= newInterval.end){
                newInterval.start = min(newInterval.start, intervals[index].start);
                newInterval.end = max(newInterval.end, intervals[index].end);
                index++;
            }
            res.push_back(newInterval);
            while(index < intervals.size()){
                res.push_back(intervals[index++]);
            }
            return res;
        }
    };