C++刷leetcode（435. 无重叠区间）【贪心思想】

糖逗

题目描述：

1. 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
   
2. 
   
3. 注意:
   
4. 
   
5. 可以认为区间的终点总是大于它的起点。
   
6. 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
   
7. 示例 1:
   
8. 
   
9. 输入: [ [1,2], [2,3], [3,4], [1,3] ]
   
10. 
    
11. 输出: 1
    
12. 
    
13. 解释: 移除 [1,3] 后，剩下的区间没有重叠。
    
14. 示例 2:
    
15. 
    
16. 输入: [ [1,2], [1,2], [1,2] ]
    
17. 
    
18. 输出: 2
    
19. 
    
20. 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
    
21. 示例 3:
    
22. 
    
23. 输入: [ [1,2], [2,3] ]
    
24. 
    
25. 输出: 0
    
26. 
    
27. 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
    
28. 
    
29. 来源：力扣（LeetCode）
    
30. 链接：https://leetcode-cn.com/problems/non-overlapping-intervals
    
31. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     static bool cmp(vector<int>a, vector<int>b){
   
4.         return a[1] < b[1];
   
5.     }
   
6.     int eraseOverlapIntervals(vector<vector<int>>& intervals) {
   
7.         sort(intervals.begin(), intervals.end(), cmp);
   
8.         int i = 0;
   
9.         int res = 0;
   
10.         while(i < intervals.size()){
    
11.             int start = intervals[i][0], end = intervals[i][1];
    
12.             i++;
    
13.             while(i < intervals.size() && intervals[i][0] < end){
    
14.                 res++;
    
15.                 i++;
    
16.             }
    
17.         }
    
18.         return res;
    
19.     }
    
20. };

复制代码

参考链接：https://leetcode-cn.com/problems ... -du-wen-ti-by-labu/