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

============

in-place one:

vector<Interval> adjustEnd(vector<Interval>& intervals, int i, Interval newInterval) {

        int j = i + 1;

        while (j <= intervals.size()) {

            if (j == intervals.size()) {

                intervals[i].end = max(newInterval.end, intervals[i].end);

                return intervals;

            }

            if (newInterval.end < intervals[j].start) {

                intervals[i].end = max(newInterval.end, intervals[i].end);

                return intervals;

            } else if (newInterval.end >= intervals[j].start &&

                        newInterval.end <= intervals[j].end) {

                intervals[i].end = intervals[j].end;

                intervals.erase(intervals.begin() + j);

                return intervals;

            } else {

                intervals.erase(intervals.begin() + j);

            }

        }

        return intervals;

    }

    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {

        if (intervals.size() == 0) {

            intervals.push_back(newInterval);

            return intervals;

        }

        int size = intervals.size();

        if (newInterval.start > intervals[size - 1].end) {

            intervals.push_back(newInterval);

            return intervals;

        }

        int i = 0;

        while (i < intervals.size()) {

            if (newInterval.start >= intervals[i].start &&

                newInterval.start <= intervals[i].end) {

                return adjustEnd(intervals, i, newInterval);

            } else if (newInterval.start < intervals[i].start) {

                if (newInterval.end < intervals[i].start) {

                    intervals.insert(intervals.begin() + i, newInterval);

                    return intervals;

                } else if (newInterval.end >= intervals[i].start) {

                    intervals[i].start = newInterval.start;

                    return adjustEnd(intervals, i, newInterval);

                }

            }

            i++;

        }

        

        return intervals;

    }


=============
Short and elegant below in java:

 public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    if(newInterval == null) return intervals;
    int first = 0;
    /*find first overlapping interval*/
    while(first < intervals.size() && newInterval.start > intervals.get(first).end)
        first++;   
    /*merge intervals */
    while(first < intervals.size() && newInterval.end >= intervals.get(first).start)
    {
        newInterval = new Interval(Math.min(newInterval.start,intervals.get(first).start),
                                  Math.max(newInterval.end,intervals.get(first).end));
        intervals.remove(first);
    }
    intervals.add(first,newInterval);
    return intervals;
}

===============  Recent one ========

class Solution {
public:
    bool overlap(vector<int> interval, int& first, int& second) {
        if ((first >= interval[0] && first <= interval[1]) ||
            (second >= interval[0] && second <= interval[1])) {
            
            first = min(interval[0], first);
            second = max(interval[1], second);
            return true;
        }
        return false;
    }

    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> sol;
        int first = newInterval[0];
        int second = newInterval[1];
        
        if (intervals.size() == 0) {
            sol.push_back(vector<int> {first, second});
            return sol;
        }
        
        int i = 0;
        bool merged = false;
        
        for (i = 0; i < intervals.size(); i++) {
            bool is_overlap = overlap(intervals[i], first, second);
            if (!is_overlap) {
                if (second < intervals[i][0]) {
                    if (!merged) {
                        sol.push_back(vector<int> {first, second});
                        merged = true;
                    }
                    sol.push_back(intervals[i]);
                } else if (intervals[i][1] < first) {
                    sol.push_back(intervals[i]);
                }
            }
        }
        
        if (!merged) {
            sol.push_back(vector<int> {first, second});
        }
        return sol;
    }

};


=========== Another one =======
class Solution {
public:
    
    int overlap(vector<int>& newInterval, vector<int>& interval) {
        if (newInterval[1] < interval[0]) {
            // newInterval < interval
            return -1;
        } else if (newInterval[0] > interval[1]) {
            // newInterval > interval
            return 1;
        } else {
            // Merge.
            return 0;
        }
    }
    
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> sol;
        if (intervals.size() == 0) {
            sol.push_back(newInterval);
            return sol;
        }
        
        int iter = 0;
        while (iter < intervals.size()) {
            int option = overlap(newInterval, intervals[iter]);
            if (option == 0) {
                // Merge going-on
                newInterval[0] = min(newInterval[0], intervals[iter][0]);
                newInterval[1] = max(newInterval[1], intervals[iter][1]);
            } else if (option == -1) {
                // merge completed.
                sol.push_back(newInterval);
                while (iter < intervals.size()) {
                    sol.push_back(intervals[iter]);
                    iter++;
                }
                return sol;
            } else {
                // Merge ahead
                sol.push_back(intervals[iter]);
            }
            iter++;
        }
        sol.push_back(newInterval);
        return sol;
    }

};