LeetCode 57. Insert Interval 插入区间 (C++/Java)

题目：

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:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

分析：

给定一个无重叠的，已排序的区间集合，要求在集合中插入一个新的区间，保证插入后区间无重叠且有序。

LeetCode 56. Merge Intervals 合并区间 (C++/Java)的进阶，我们可以利用56题的解法来解决这道题，也就是在原列表中按序将新区间插入，然后再进行区间合并。

此外我们还可以将原集合区间分为三部分，一部分是右端点小于新区间左端点，一部分是左端点大于新区间右端点，这两部分区间不会和新区间发生合并，剩下的区间则需要和新区间合并，遍历完所有区间后，将三部分合并即可。

C++采用插入排序合并，Java采用分区合并

程序：

C++

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        auto it = intervals.begin();
        while(it != intervals.end() && (*it)[0] < newInterval[0])
            it++;
        intervals.insert(it, newInterval);
        vector<vector<int>> res;
        for(auto interval:intervals){
            if(res.empty())
                res.push_back(interval);
            else if(res.back()[1] < interval[0])
                res.push_back(interval);
            else{
                auto t = res.back();
                res.pop_back();
                res.push_back({t[0], max(t[1], interval[1])});
            }
        }
        return res;
            
    }
};

Java

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {

        int start = newInterval[0];
        int end = newInterval[1];
        List<int[]> l = new ArrayList<>();
        List<int[]> r = new ArrayList<>();
        for(int[] interval:intervals){
            if(interval[1] < start){
                l.add(interval);
            }else if(end < interval[0]){
                r.add(interval);
            }else{
                start = Math.min(start, interval[0]);
                end = Math.max(end, interval[1]);
            }
        }
        l.add(new int[]{start, end});
        l.addAll(r);
        return l.toArray(new int[l.size()][]);
    }
}