[LeetCode] 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].

思路：

遍历input list。如果当前interval < newInterval, add当前；如果当前interval > newInterval, add new Interval; 若重叠，则合并成新的new interval.

Java:

/**

 * Definition for an interval.

 * public class Interval {

 *     int start;

 *     int end;

 *     Interval() { start = 0; end = 0; }

 *     Interval(int s, int e) { start = s; end = e; }

 * }

 */

public class Solution {

    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {

        Interval temp = newInterval;

        ArrayList<Interval> lst = new ArrayList<Interval>();

        

        for(Interval i : intervals){

            if(i.end < temp.start){

                lst.add(i);

            }

            else if(i.start > temp.end){

                lst.add(temp);

                temp = i;

            }

            else{

                temp = new Interval(Math.min(temp.start, i.start), Math.max(temp.end, i.end));

            }

        }

        

        lst.add(temp);

        

        return lst;

    }

}

C++:

/**

 * 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) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        Interval temp = newInterval;
        vector<Interval> v;

        

        for(int i = 0; i < intervals.size(); i++){
            if(intervals[i].start > temp.end){
                v.push_back(temp);
                temp = intervals[i];
            }
            else if(intervals[i].end < temp.start){
                v.push_back(intervals[i]);
            }
            else{
                temp.start = min(temp.start, intervals[i].start);
                temp.end = max(temp.end, intervals[i].end);
            }
        }
        v.push_back(temp);
        return v;
    }
};