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

糖逗

题目描述：

1. 给出一个区间的集合，请合并所有重叠的区间。
   
2. 
   
3. 示例 1:
   
4. 
   
5. 输入: [[1,3],[2,6],[8,10],[15,18]]
   
6. 输出: [[1,6],[8,10],[15,18]]
   
7. 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
   
8. 示例 2:
   
9. 
   
10. 输入: [[1,4],[4,5]]
    
11. 输出: [[1,5]]
    
12. 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
    
13. 
    
14. 来源：力扣（LeetCode）
    
15. 链接：https://leetcode-cn.com/problems/merge-intervals
    
16. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <string>
   
2. #include <vector>
   
3. #include <iostream>
   
4. #include <algorithm>
   
5. 
   
6. using namespace std;
   
7. 
   
8. 
   
9. vector<vector<int>> solution(vector<vector<int>>& input) {
   
10.     vector<vector<int> > res;
    
11.     int len = input.size();
    
12.     if(len == 0 || len == 1) return input;
    
13.     sort(input.begin(), input.end());
    
14.     int left = input[0][0], right = input[0][1];
    
15. 
    
16.     for(int i = 1; i < len; i++){
    
17.         if(input[i][0] >= left && input[i][0]<= right || input[i][0] == left){
    
18.             right = max(input[i][1], right);
    
19.             if(!res.empty()) res.pop_back();
    
20.             res.push_back({left, right});
    
21.         }
    
22.         else{
    
23.             if(i == 1){
    
24.                 res.push_back(input[0]);
    
25.             }
    
26.             res.push_back(input[i]);
    
27.             right = input[i][1];
    
28.             left = input[i][0];
    
29. 
    
30.         }
    
31.     }
    
32.     return res;
    
33.    
    
34. }
    
35. 
    
36. 
    
37. int main(void){
    
38.         int row;
    
39.         cin >> row;
    
40.         cin.clear();
    
41.         vector<vector<int> > input;
    
42.         int number;
    
43.         input.resize(row);
    
44.         for(int i = 0; i < row; i++){
    
45.                 for(int j = 0 ; j < 2; j++){
    
46.                         cin >> number;
    
47.                         input[i].push_back(number);
    
48.                 }
    
49.         }
    
50.        
    
51.         vector<vector<int> > res  = solution(input);
    
52.         for(int i = 0; i < res.size(); i++){
    
53.                 for(int j = 0; j < res[0].size(); j++){
    
54.                         cout << res[i][j] << " ";
    
55.                 }
    
56.                 cout << endl;
    
57.         }
    
58. 
    
59.         return 0;
    
60. }

复制代码

注意事项：
1.sort排序。