57. 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
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
| class Solution { public: vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) { if(intervals.empty()) { return vector<vector<int>>{newInterval}; } else if(intervals.front()[0] > newInterval[1]) { intervals.insert(intervals.begin(), newInterval); return intervals; } else if(intervals.back()[1] < newInterval[0]) { intervals.push_back(newInterval); return intervals; }
int startPos = intervals.size() - 1, endPos = intervals.size() - 1; for(int i = 0; i < intervals.size(); i++) { if(intervals[i][1] >= newInterval[0]) { startPos = min(startPos, i); }
if(intervals[i][0] > newInterval[1]) { endPos = min(endPos, i - 1); break; } }
intervals.insert(intervals.begin() + startPos, vector<int>{min(intervals[startPos][0], newInterval[0]), max(intervals[endPos][1], newInterval[1])}); intervals.erase(intervals.begin() + startPos + 1, intervals.begin() + endPos + 2);
return intervals; } };
|