C++刷leetcode（56. 合并区间）

糖逗

题目描述：

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

示例 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] 可被视为重叠区间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;


vector<vector<int>> solution(vector<vector<int>>& input) {
    vector<vector<int> > res;
    int len = input.size();
    if(len == 0 || len == 1) return input;
    sort(input.begin(), input.end());
    int left = input[0][0], right = input[0][1];

    for(int i = 1; i < len; i++){
        if(input[i][0] >= left && input[i][0]<= right || input[i][0] == left){
            right = max(input[i][1], right);
            if(!res.empty()) res.pop_back();
            res.push_back({left, right});
        }
        else{
            if(i == 1){
                res.push_back(input[0]);
            }
            res.push_back(input[i]);
            right = input[i][1];
            left = input[i][0];

        }
    }
    return res;
    
}


int main(void){
        int row;
        cin >> row;
        cin.clear();
        vector<vector<int> > input;
        int number;
        input.resize(row);
        for(int i = 0; i < row; i++){
                for(int j = 0 ; j < 2; j++){
                        cin >> number;
                        input[i].push_back(number);
                }
        }
        
        vector<vector<int> > res  = solution(input); 
        for(int i = 0; i < res.size(); i++){
                for(int j = 0; j < res[0].size(); j++){
                        cout << res[i][j] << " "; 
                }
                cout << endl;
        } 

        return 0;
}

注意事项：
1.sort排序。