Given a non-overlapping interval list which is sorted by start point.
Insert a new interval into it, make sure the list is still in order andnon-overlapping (merge intervals if necessary).
Example
Insert [2, 5] into [[1,2], [5,9]], we get [[1,9]].
Insert [3, 4] into [[1,2], [5,9]], we get [[1,2], [3,4], [5,9]].
/** * Definition of Interval: * classs Interval { * int start, end; * Interval(int start, int end) { * this->start = start; * this->end = end; * } */ class Solution { public: static bool comp(Interval i1, Interval i2) { return i1.start < i2.start; } Interval merge(Interval &i1, Interval &i2) { Interval res(min(i1.start, i2.start), max(i1.end, i2.end)); return res; } bool hasOverlap(Interval &i1, Interval &i2) { if(i1.end < i2.start || i2.end < i1.start) return false; return true; } vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { sort(intervals.begin(), intervals.end(), comp); vector<Interval> res; for(int i=0;i<intervals.size();i++) { if(hasOverlap(intervals[i], newInterval)) { newInterval = merge(intervals[i], newInterval); } else { res.push_back(intervals[i]); } } int i=0; while(i<res.size() && newInterval.end>res[i].start) i++; res.insert(res.begin()+i, newInterval); return res; } };