题解 | #合并区间#

class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        if(intervals.size() <= 1){
            return intervals;
        }
        
        vector<Interval> res;
//         for(int i =0;i<intervals.size();i++){
//             for(int j=1;j<intervals.size()-i;j++){
//                 if(intervals[j].start < intervals[j-1].start){
//                     Interval tmp = intervals[j];
//                     intervals[j] = intervals[j-1];
//                     intervals[j-1] = tmp;
//                 }
//             }
//         }
        
        intervals = quickSort(intervals);
        res = {intervals[0]};
        for(int i=1;i<intervals.size();i++){
            Interval last = res[res.size()-1];
            if(intervals[i].start <= last.end){
                last.end = max(intervals[i].end, last.end);
                res[res.size()-1] = last;
            }else{
                res.push_back(intervals[i]);
            }
        }
        
        return res;
    }
    
     vector<Interval> quickSort(vector<Interval> &intervals){
         if(intervals.size() <= 1){
             return intervals;
         }
         
         vector<Interval> left = {};
         vector<Interval> right = {};
         for(int i=1;i<intervals.size();i++){
             if(intervals[i].start > intervals[0].start){
                 right.push_back(intervals[i]);
             }else{
                 left.push_back(intervals[i]);
             }
         }
         
         left = quickSort(left);
         right = quickSort(right);
         left.push_back(intervals[0]);
         left.insert(left.end(), right.begin(), right.end());
         return left;
     }
};