57 Insert Interval——leetcode

57	Insert Interval

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
 bool overlap(const Interval &left,const Interval &right){
    return !(left.end<right.start||right.end<left.start);
}
struct Overlap:public std::binary_function<Interval,Interval,bool>{
    bool operator()(const Interval &left,const Interval&right)const{
        return !(left.end<right.start||right.end<left.start);
    }
};
struct IntervalCompare:public std::binary_function<Interval,Interval,bool>{
    bool operator()(const Interval &left,const Interval&right)const{
        return left.start<right.start;
    }
};
class Solution {
public:
 vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> ans;
        
        ans.reserve(intervals.size());
        if(intervals.empty()){
            ans.push_back(newInterval);
            return ans;
        }
        // std::sort(intervals.begin,intervals.end(),IntervalCompare());
        int i=0;
        Interval merge = intervals[0];
        vector<Interval> &merges=intervals;
        merge = newInterval;
        
        if(newInterval.end<merges[0].start)
        {
        }
        else
        {
            for(i=0;i<merges.size();i++)
            {
                if(Overlap()(merge,merges[i]))
                {
                    merge.start = std::min(merge.start,merges[i].start);
                    merge.end = std::max(merge.end,merges[i].end);
                }
                else
                {
                    if(merge.end<merges[i].start){
                        break;
                    }
                    ans.push_back(merges[i]);
                }
            }
        }
        ans.push_back(merge);
        ans.insert(ans.end(),merges.begin()+i,merges.end());
        return ans;
    }
};

 

这个其实，像扫描线（sweep）算法（在二维计算几何中，经常用到）

基本思路：注意到已经按照每个Interval的start排序了

<1>将需要检查的newInterval，依次和每个interval合并（循环）

<2>如果发现没有重叠，跳出

<3>添加合并后的merge 区间，添加哪些不与newInterval重叠的区间。

 

上述，很容易理解，但有个问题：

为什么保证结果一定有序？即按照区间的start排序？

其实，这是因为，<1>中基本上属于插入排序过程，所以结果一定有序。