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

Approach: First find the place for the newly arrived interval in the existing intervals. Then perform the approach used in this problem.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

/** * 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) { int i = 0; int n = intervals.size(); vector<Interval> out; //find the location of new interval while(i < n && intervals[i].start < newInterval.start){ i++; } //add the vector at the specified location intervals.insert(intervals.begin() + i, newInterval); //merge the possible intervals stack<Interval> it; it.push(intervals[0]); n = intervals.size(); for(int i = 1; i < n; i++){ Interval topInterval = it.top(); //if start time of next is after the end of the prev, push the next if(intervals[i].start > topInterval.end){ it.push(intervals[i]); }else if(intervals[i].end > topInterval.end){ //if start time of next is before the end of the prev and the end of the next is after the end of the prev, then update the end of the prev topInterval.end = intervals[i].end; it.pop(); it.push(topInterval); } } while(!it.empty()){ Interval curr = it.top(); out.push_back(curr); it.pop(); } //reverse to get the output reverse(out.begin(), out.end()); return out; } };