leetcode每日一题复盘(11.13~11.19)

一题复盘(11.13~11.19)"/>

leetcode每日一题复盘(11.13~11.19)

leetcode 435 无重叠区间

本题和射气球最小箭数大同小异，但是这一题没做出来，难就难在题目如何理解:移除区间最小数量，使剩下的区间不重叠

那么本质上就是求最少有多少个重叠区间，把重叠区间去掉剩下的区间即不重叠

这里有两种做法，不同在于数组的排序方式，也就是获取重叠区间的方法不一样

第一种是以结束下标为依据,小的排在前面,用其他区间的开始下标和结束下标进行比较,如果开始下标小于结束下标,说明两个区间重叠,当开始下标大于等于结束下标时说明有新的非重叠区间,数量+1

结果以两者之差返回

个人比较偏向于第二种方法,直接统计重叠的区间数量

第二种方法以开始区间为排序依据,结束下标小的排在前面,用结束下标和开始下标进行比较,如果结束下标大于开始下标说明区间重叠,并更新结束下标的值,否则说明区间不重叠

两种方法大同小异,比较的方法都相同,不同在于排序的方法和统计的目标