bm89.合并区间

1
2
3
4
5

输入：
[[10,30],[20,60],[80,100],[150,180]]
 
返回值：
[[10,60],[80,100],[150,180]]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

/**
 * 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:
    static bool cmp(Interval&x, Interval &y) {
        if(x.start == y.start) return x.end < y.end;
        return x.start < y.start;
    }
    vector<Interval> merge(vector<Interval> &intervals) {
        if(intervals.size() <=1) return intervals;
        sort(intervals.begin(),intervals.end(),cmp );
        int n = intervals.size();
        vector<Interval> res;
        res.push_back(intervals[0]);
        for(int i=0;i<n;i++) {
            int l = intervals[i].start,r = intervals[i].end;
            if(res.back().end < l) {
                // 不相交
                res.push_back(intervals[i]);
            }else if(res.back().end >= l) {
                res.back().end = max(r,res.back().end);// merge
            } 
            
        }
        
        return res;
        
    }
};