[leetcode]Merge Intervals

先写了一个O(n^2)的算法

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<Interval> result;
        if(intervals.empty()) return result;
        
        Interval newInterval;
        
        for(int i = 0; i < intervals.size(); i++){
            newInterval = intervals[i];
            result = insert(result, newInterval);
        }
        return result;
        
    }
    
     vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<Interval> pre;
        vector<Interval> post;
        
        int low = newInterval.start;
        int high = newInterval.end;
        
        for(int i = 0; i < intervals.size(); i++){
            if(intervals[i].end < low){
                pre.push_back(intervals[i]);
            }
            if(intervals[i].start > high){
                post.push_back(intervals[i]);
            }
        }
        
        int p;
        
        if(intervals.empty() || pre.size() == intervals.size()){
            p = low;
        }else{
            p = min(low, intervals[pre.size()].start);
        }
        
        int q;
        if(intervals.empty() || post.size() == intervals.size()){
            q = high;
        }else{
            q = max(high, intervals[intervals.size()-1-post.size()].end);
        }
        
        pre.push_back(Interval(p,q));
        pre.insert(pre.end(), post.begin(), post.end());
        
        return pre;
        
    }
};

然后翻看我以前写的，发现其实O(nlogn)就可以解决这个问题了

只要先按照start来排个序，这样每次记住前一个interval，就可以不用过去遍历之前的那些已经排好的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 intervalLessThan(const Interval &i1, const Interval &i2){
        return (i1.start < i2.start);
    }
 
 
class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<Interval> f;
        if(intervals.empty()) return f;
        sort(intervals.begin(),intervals.end(),intervalLessThan);
        
        Interval pre = intervals[0];
        
        for(int i = 0; i < intervals.size(); i++){
            Interval &cur = intervals[i];
            if(pre.end < cur.start){
                f.push_back(pre);
                pre = cur;
                continue;
            }
            pre.start = min(pre.start, cur.start);
            pre.end = max(pre.end, cur.end);
        }
        
        if(f.empty() || f.back().end < pre.start) f.push_back(pre);
        
        return f;
        
    }
};

果真，第一个方法大集合100ms，第二个方法68ms