【学习笔记】LeetCode 435 无重叠区间（贪心区间）

LeetCode 435

class Solution { public int eraseOverlapIntervals(int[][] intervals) { if(intervals.length==0) return 0; //对end排序 Arrays.sort(intervals,((o1, o2) -> o1[1]-o2[1])); int sum=0; int end=intervals[0][1]; for(int i=1;i<intervals.length;i++){ int start=intervals[i][0]; if(start<end) sum++; else end=intervals[i][1]; } return sum; } }

一个很基础的贪心题目，学习过程中唯一的疑问就是为什么要对end排序而不是start排序

我的看法：end小start一定小，因为start<end，但是end大不一定start大，可能有一个区间start是所有start最小的，end是最大的，这样把所有其他区间都覆盖了。

对end排序相当于保证了start的顺序。