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

Hide Tags

 Array Sort

Show Similar Problems

----------------------------------------------------------------------------------

Basically there are three cases in this implementation. see the plot below: 

case 1 and 2 are easy as no merge occurs. but for case two, there are overlapping with each other. In case two, there are also there sub-classes, but we can classify all these sub-classes into one but using the the judgement: s1, s2 and s3 are all <=e &&  e1, e2 and e3 are all >=s. this can simplify the procedure. 

So in the codes:

1. when meet case 1 and 3, insert the intervals[i] directly;

2. when meet case 2, on insertion is needed, but the newInterval  should be updated with new boundaries when compared to the intervals[i];

///////////////////////////

//codes

class Solution {

public:

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

              vector<Interval> ret;

              bool isInsert = false;

              for (int i = 0; i<intervals.size(); i++) {

                     // already insert newInterval

                     if (isInsert) {

                           ret.push_back(intervals[i]);

                           continue;

                     }

                     // insert newInterval before current interval

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

                           ret.push_back(newInterval);

                           ret.push_back(intervals[i]);

                           isInsert = true;

                           continue;

                     }

                     // combine newInterval with current interval

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

                           newInterval.start = min(newInterval.start, intervals[i].start);

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

                           continue;

                     }

                     // newInterval after current interval

                     ret.push_back(intervals[i]);

              }

              if (!isInsert) ret.push_back(newInterval);

              return ret;

       }

};