code
/**
* Definition of Interval:
* class Interval {
* public:
* int start, end;
* Interval(int start, int end) {
* this->start = start;
* this->end = end;
* }
* }
*/
class Solution {
public:
/**
* Insert newInterval into intervals.
* @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
int i = 0, size = intervals.size();
if(size == 0) {
intervals.push_back(newInterval);
return intervals;
}
while(i<size && compareInterval(newInterval, intervals[i])) {
++i;
}
intervals.insert(intervals.begin()+i, newInterval);
size = intervals.size();
for(i=0; i<size-1; i++) {
// intervals[i+1] 属于 intervals[i]，檫除intervals[i+1]
if(intervals[i+1].start >= intervals[i].start && intervals[i+1].end <= intervals[i].end) {
intervals.erase(intervals.begin()+i+1);
size--;
i--;
}
// intervals[i+1] 与 intervals[i]合并
else if(intervals[i+1].start <= intervals[i].end){
intervals[i].end = intervals[i+1].end;
intervals.erase(intervals.begin()+i+1);
size--;
i--;
}
}
return intervals;
}
// @return 1:a>b
// @return 0:a<=b
bool compareInterval(Interval &a, Interval &b){
if(a.start == b.start) {
return a.end > b.end;
}
return a.start > b.start;
}
};