leetcode/Merge_Intervals.cpp at master · whodewho/leetcode · GitHub

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
37
38
39
/*
  O(N*log(N))
 */

struct StartIncreasing {
    bool operator()(const Interval &a, const Interval &b) {
        return a.start < b.start;
    }
} start_increasing;


vector<Interval> merge(vector<Interval> &intervals) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function

    //sort(intervals.begin(), intervals.end(), compare);
    //this does not work, but in eclipse, it's ok
    sort(intervals.begin(), intervals.end(), start_increasing);

    vector<Interval> res;
    for (int i = 0; i < intervals.size(); i++) {
        if (res.empty()) {
            res.push_back(intervals[i]);
        } else {
            int j = res.size() - 1;
            if (intervals[i].start > res[j].end) {
                res.push_back(intervals[i]);
                continue;
            } else {
                if (intervals[i].end <= res[j].end) {
                    continue;
                } else {
                    res[j].end = intervals[i].end;
                }
            }
        }
    }
    return res;
}