56 Merge Intervals——leetcode

这个是基于排序库实现的

56	Merge Intervals

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
 struct Overlap{
    bool operator()(const Interval &left,const Interval&right)const{
        return !(left.end<right.start||right.end<left.start);
    }
};
bool overlap(const Interval &left,const Interval &right){
    return !(left.end<right.start||right.end<left.start);
}

struct IntervalCompare{
    bool operator()(const Interval &left,const Interval&right)const{
        return left.start<right.start;
    }
};

class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        if(intervals.empty()){
            return intervals;
        }
        std::sort(intervals.begin(),intervals.end(),IntervalCompare());
        int i=0;
        Interval *merge = &intervals[0];
        vector<Interval> merges;
        int merged_i=0;
        for(i=1;i<intervals.size();i++)
        {
            if(Overlap()(*merge,intervals[i]))
            {
                merge->end = std::max(merge->end,intervals[i].end);
            }
            else
            {
                if(merged_i!=i)
                {
                    intervals[merged_i] = *merge;
                }
                ++merged_i;
                
                merge = &intervals[i];
            }
        }
        if(merged_i!=i)
        {
           intervals[merged_i] = *merge; 
        }
        ++merged_i;
        intervals.resize(merged_i);
        return intervals;
    }
};

 同样是合并，没有太大的区别。这里使用了排序库函数，核心在排序。