30. Insert Interval
class Solution {
public:
/**
* @param intervals: Sorted interval list.
* @param newInterval: new interval.
* @return: A new interval list.
*/
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
// write your code here
// ()[]()，几种情况：
//([)]() = {}(), ()[](), ()([)(]) = (){}，找到需要merge的，放置的index
vector<Interval> res;
int pos;
for(Interval each : intervals){
if(each.end < newInterval.start){
pos++;
res.push_back(each); //在新区间左边的
}
else if(newInterval.end < each.start){
res.push_back(each); //在新区间右边的
}
else{
newInterval.start = min(newInterval.start, each.start);
newInterval.end = max(newInterval.end, each.end); //组成的新区间
}
}
res.insert(res.begin() + pos, newInterval); //最后插入组成的新区间
return res;
}
};
Comments
Post a Comment