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].
1 /** 2 * Definition for an interval. 3 * struct Interval { 4 * int start; 5 * int end; 6 * Interval() : start(0), end(0) {} 7 * Interval(int s, int e) : start(s), end(e) {} 8 * }; 9 */10 class Solution {11 private:12 vector ret;13 public:14 vector insert(vector &intervals, Interval newInterval) {15 // Start typing your C/C++ solution below16 // DO NOT write int main() function17 ret.clear();18 bool inserted = false;19 if (intervals.size() == 0)20 {21 inserted = true;22 ret.push_back(newInterval);23 }24 25 int i = 0;26 while (i < intervals.size())27 {28 if (ret.size() == 0)29 {30 if (intervals[i].start < newInterval.start)31 {32 ret.push_back(intervals[i]);33 i++;34 }35 else36 {37 inserted = true;38 ret.push_back(newInterval);39 }40 }41 else42 {43 int size = ret.size();44 if (inserted)45 {46 if (ret[size-1].start <= intervals[i].start && intervals[i].start <= ret[size-1].end)47 ret[size-1].end = max(ret[size-1].end, intervals[i].end);48 else49 ret.push_back(intervals[i]);50 i++;51 }52 else53 {54 if (newInterval.start < intervals[i].start)55 {56 inserted = true;57 if (ret[size-1].start <= newInterval.start && newInterval.start <= ret[size-1].end)58 ret[size-1].end = max(ret[size-1].end, newInterval.end);59 else60 ret.push_back(newInterval);61 }62 else63 {64 if (ret[size-1].start <= intervals[i].start && intervals[i].start <= ret[size-1].end)65 ret[size-1].end = max(ret[size-1].end, intervals[i].end);66 else67 ret.push_back(intervals[i]);68 i++;69 }70 }71 }72 }73 74 if (!inserted)75 {76 int size = ret.size();77 if (ret[size-1].start <= newInterval.start && newInterval.start <= ret[size-1].end)78 ret[size-1].end = max(ret[size-1].end, newInterval.end);79 else80 ret.push_back(newInterval);81 }82 83 return ret; 84 }85 };