程序员

lintcode第三十题 插入空间

给出一个无重叠的按照区间起始端点排序的区间列表。
在列表中插入一个新的区间,你要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。
插入区间[2, 5] 到 [[1,2], [5,9]],我们得到 [[1,9]]。
插入区间[3, 4] 到 [[1,2], [5,9]],我们得到 [[1,2], [3,4], [5,9]]。
遍历比大小,直接上代码:

/**
 * 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 insert(vector &intervals, Interval newInterval) {
        // write your code here
        if (intervals.empty()) {  
            intervals.push_back(newInterval);  
            return intervals;  
        }  
        int i = 0;  
        while (i < intervals.size() && cmp(newInterval,intervals[i])) {  
            i++;  
        }  
        intervals.insert(intervals.begin() + i,newInterval);  
        for (int j = 0;j < intervals.size() - 1;j++) {  
            if (intervals[j+1].start >= intervals[j].start && intervals[j+1].end <= intervals[j].end) {  
                intervals.erase(intervals.begin() + j + 1);  
                j--;  
            }  
            else if(intervals[j+1].start <= intervals[j].end) {  
                intervals[j].end = intervals[j+1].end;  
                intervals.erase(intervals.begin()+ j + 1);  
                j--; 
            }  
        }
        return intervals;  
    }
    bool cmp(Interval &a,Interval &b) {  
        if(a.start == b.start)  
            return a.end > b.end;  
        return a.start > b.start;      
    } 
};