leetcode/56.cpp at main · Aqiu16717/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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) {
            return {};
        }
        if (intervals.size() == 1) {
            return intervals;
        }
        // O(nlogn)
        std::sort(intervals.begin(), intervals.end(),
            [](const vector<int>& lhs, const vector<int>& rhs) {
                return lhs[0] == rhs[0] ? lhs[1] < rhs[1] : lhs[0] < rhs[0];
            });
        vector<vector<int>> ret;
        int start = intervals[0][0];
        int end = intervals[0][1];
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i][0] <= end) {
                end = max(end, intervals[i][1]);
            } else {
                ret.push_back({start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            }
            if (i == intervals.size() - 1) {
                ret.push_back({start, end});
            }
        }
        return ret;
    }
};
/**
[1,3],[2,6],[8,10],[15,18]
|----|
1    3
  |------|
  2      6
            |------|
            8      10
                        |-----|
                        15    18
**/

class SolutionV2 {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) {
            return {};
        }
        // O(nlogn)
        std::sort(intervals.begin(), intervals.end(),
            [](const vector<int>& lhs, const vector<int>& rhs) {
                //return lhs[0] == rhs[0] ? lhs[1] < rhs[1] : lhs[0] < rhs[0];
                return lhs[0] < rhs[0];
            });
        vector<vector<int>> ret;
        // int start = intervals[0][0];
        // int end = intervals[0][1];
        ret.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i][0] <= ret.back()[1]) {
                ret.back()[1] = max(ret.back()[1], intervals[i][1]);
            } else {
                ret.push_back(intervals[i]);
            }
        }
        return ret;
    }
};

int main()
{
    Solution s;
    vector<vector<int>> x = {{1,4},{0,2},{3,5}};
    vector<vector<int>> ret = s.merge(x);
    cout << "expect:\t[0,5]" << endl;
    cout << "ret:\t";
    for (const auto& vec : ret) {
        cout << "[ ";
        for (const auto& elem : vec) {
            cout << elem << ", ";
        }
        cout << "] ";
    }
    cout << endl;
    return 0;
}