Insert Interval -- Leetcode

[Question]
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].
[Analysis]
Because all intervals are sorted and non-overlapping, for intervals A and B, if A.start < B.start, A.end < B.end.  Need to find the first and the last interval in the sequence that overlaps with the given interval.

One scan on the array of intervals can complete the replacement. Time complexity is O(N). There is no need for extra storage (shown in the 2nd code sample below). The 3rd code sample shows how binary search can help to improve time complexity of locating the overlapping range of intervals.

[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) {}
 * };
 */
//---  (1) This solution use O(N) extra storage.
//---        The input intervals vector is not changed
class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        if (intervals.empty())  return vector<Interval>(1, newInterval);
     
        vector<Interval> ret;
        int i,j;
        for (i=0; i<intervals.size(); i++) {
            if (intervals[i].end < newInterval.start) {
                ret.push_back(intervals[i]);
            }
            else break;
        }
     
        for (j=intervals.size()-1; j>=0; j--) {
            if (intervals[j].start <= newInterval.end)
                break;
        }          
     
        if (i<=j)  {
            newInterval.start = min (newInterval.start, intervals[i].start);
            newInterval.end = max (newInterval.end, intervals[j].end);
        }
        ret.push_back(newInterval);
     
        for (int k=j+1; k< intervals.size(); k++) {
            ret.push_back( intervals[k] );
        }
     
        return ret;
    }
};

//--- (2) This solution is in-place.
//---       The input "intervals" are modified accordingly.
class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        if (intervals.empty()) {
            intervals.push_back(newInterval);
            return intervals;
        }
     
        if (intervals[0].start > newInterval.end) {
            intervals.insert (intervals.begin(), newInterval);
            return intervals;
        }
     
        if (intervals.back().end < newInterval.start) {
            intervals.push_back(newInterval);
            return intervals;
        }
     
        int iStart = 0;
        for (int i=0; i<intervals.size(); i++) {
            if (newInterval.start <= intervals[i].end) {
                iStart = i;
                break;
            }
        }

        int iEnd = 0;
        for (int i=intervals.size()-1; i>=0; i--) {
            if (newInterval.end >= intervals[i].start) {
                iEnd = i;
                break;
            }
        }
             
        newInterval.start = min(newInterval.start, intervals[iStart].start);
        newInterval.end   = max(newInterval.end, intervals[iEnd].end);
     
        intervals.erase(intervals.begin()+iStart, intervals.begin()+iEnd+1);
        intervals.insert(intervals.begin()+iStart, newInterval);
     
        return intervals;
    }
};

//--- (3) Use binary search: lower_bound() in STL.
class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        if (intervals.empty()) {
            intervals.push_back(newInterval);
            return intervals;
        }
     
        if (intervals[0].start > newInterval.end) {
            intervals.insert (intervals.begin(), newInterval);
            return intervals;
        }
     
        if (intervals.back().end < newInterval.start) {
            intervals.push_back(newInterval);
            return intervals;
        }

        int iStart = lower_bound(intervals.begin(), intervals.end(), newInterval,
                [](const Interval& a, const Interval& t) { return t.start > a.end; } ) - intervals.begin();
     
        int iEnd = lower_bound(intervals.begin(), intervals.end(), newInterval,
                [](const Interval& a, const Interval& t) { return t.end >= a.start; } ) - intervals.begin()-1;
             
        newInterval.start = min(newInterval.start, intervals[iStart].start);
        newInterval.end   = max(newInterval.end, intervals[iEnd].end);
     
        intervals.erase(intervals.begin()+iStart, intervals.begin()+iEnd+1);
        intervals.insert(intervals.begin()+iStart, newInterval);
     
        return intervals;
    }
};

Merge Intervals -- Leetcode

[Question]
Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

[Analysis]

If all intervals are sorted by their start points, the overlapping between two consecutive intervals A and B is simple: A.end > B.start. If B.start> A.end, B and the following intervals have no overlapping with A. Therefore, sort the intervals first, then scan the sorted interval list and merge them one by one when possible. The time complexity is O(N x log N + N).

Without sorting, the overlapping cases among intervals are complicated. It can not be done by one pass.

[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:
    bool intersected( const Interval& a, const Interval& b) {
        return !(a.start>b.end || b.start>a.end);
    }
 
    vector<Interval> merge(vector<Interval> &intervals) {
        if (intervals.empty()) return intervals;
       
        sort(intervals.begin(), intervals.end(),
            [](Interval a, Interval b) { return a.start < b.start; }
        );
       
        int size = intervals.size();
        Interval temp (intervals[0].start, intervals[0].end);
        for (int i=1; i<size; i++) {
            if ( intersected(intervals[i], temp) ){
                temp.start = min(intervals[i].start, temp.start);
                temp.end = max(intervals[i].end, temp.end);
            }
            else {
                intervals.push_back(temp);
                temp = intervals[i];
            }
        }
        intervals.push_back(temp);
        intervals.erase(intervals.begin(), intervals.begin()+size);
        return intervals;
    }
};