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 public:12 vectorinsert(vector &intervals, Interval newInterval) 13 {14 vector res;15 if(intervals.empty())16 {17 res.push_back(newInterval);18 return res;19 }20 21 for(int i=0;i intervals[i].end)34 res.push_back(intervals[i]);35 else36 {37 newInterval.start=min(newInterval.start,intervals[i].start);38 newInterval.end=max(newInterval.end,intervals[i].end);39 }40 }41 res.push_back(newInterval);42 return res; 43 }44 };