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.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]
Example 2:
Input: intervals =[[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval =[4,8]Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval[4,8]overlaps with[3,5],[6,7],[8,10].
把要插入的元素插入，然后调用上一个题的merge
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 public: 12 static bool sfun(Interval a,Interval b){ 13 return a.start<b.start; 14 } 15 vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) { 16 vector<Interval> res; 17 intervals.push_back(newInterval); 18 sort(intervals.begin(),intervals.end(),sfun); 19 res.push_back(intervals[0]); 20 for(int i = 1;i < intervals.size(); i++ ){ 21 Interval pre = res.back();//// 22 Interval now = intervals[i]; 23 if(now.start >pre.end ) 24 res.push_back(now); 25 else{ 26 res.back().start = pre.start; 27 res.back().end = max(now.end,pre.end); 28 29 } 30 } 31 return res; 32 } 33 };