LeetCode 56: 合并区间

[guodongxiaren]

https://leetcode-cn.com/problems/merge-intervals 合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

[guodongxiaren]

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> segments;
        for (auto& interval: intervals) {
            if (segments.size() == 0 
                || segments.back().back() < interval[0]) {
                segments.push_back(interval);
            } else if (segments.back().back() < interval[1]){
                segments.back().back() = interval[1];
            }
        }
        return segments;  
    }
};

时间复杂度：Nlog(N) 主要是快排的损耗。

[guodongxiaren]

值得一提的是。sort默认就可以对二维vector排序！默认排序方式是按照每个一维vector度首元素排序。 参见：

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<iostream>
using namespace std;

int main()
{
    vector<vector<int>> vv(10);
    for (int i = 0; i < 10;i++) {
        for (int j = 0; j < 10; j++){
            vv[i].push_back(rand()%100);
        }
    }
    for (int i = 0; i < 10; i++){
        for (int j = 0; j < 10; j++){
            cout << vv[i][j] << "\t";
        }
        cout << endl;
    }
    cout << "排序后的输出" << endl;

    sort(vv.begin(), vv.end());//默认为从小到大排序
    for (int i = 0; i < 10; i++){
        for (int j = 0; j < 10; j++){
            cout << vv[i][j] << "\t";
        }
        cout << endl;
    }

    return 0;
}

7   49  73  58  30  72  44  78  23  9
40  65  92  42  87  3   27  29  40  12
3   69  9   57  60  33  99  78  16  35
97  26  12  67  10  33  79  49  79  21
67  72  93  36  85  45  28  91  94  57
1   53  8   44  68  90  24  96  30  3
22  66  49  24  1   53  77  8   28  33
98  81  35  13  65  14  63  36  25  69
15  94  29  1   17  95  5   4   51  98
88  23  5   82  52  66  16  37  38  44
排序后的输出
1   53  8   44  68  90  24  96  30  3
3   69  9   57  60  33  99  78  16  35
7   49  73  58  30  72  44  78  23  9
15  94  29  1   17  95  5   4   51  98
22  66  49  24  1   53  77  8   28  33
40  65  92  42  87  3   27  29  40  12
67  72  93  36  85  45  28  91  94  57
88  23  5   82  52  66  16  37  38  44
97  26  12  67  10  33  79  49  79  21
98  81  35  13  65  14  63  36  25  69