LeetCode0435.Non-overlappingIntervals没有重叠区间[Medium][Python][intervalgreedy]删除以使其余间隔不重叠。示例1：输入：[[1,2],[2,3],[3,4],[1,3]]输出：1解释：[1,3]可以删除，其余间隔不重叠。示例2：输入：[[1,2],[1,2],[1,2]]输出：2解释：您需要删除两个[1,2]使其余间隔不重叠。示例3：输入：[[1,2],[2,3]]输出：0解释：您不需要删除任何间隔，因为它们已经存在不重叠。注意：您可以假设区间的终点总是大于起点。[1,2]和[2,3]之类的间隔具有“接触”的边界，但它们不会相互重叠。问题给定一组区间，找到需要删除的最小区间数，以使剩余的区间不重叠。示例1：输入：[[1,2],[2,3],[3,4],[1,3]]输出：1解释：移除[1,3]后，剩余区间不重叠。示例2：输入：[[1,2],[1,2],[1,2]]输出：2解释：您需要删除两个[1,2]以使剩余的区间不重叠。示例3：输入：[[1,2],[2,3]]输出：0解释：您不需要删除任何区间，因为它们已经不重叠。注意：可以认为一个区间的终点总是大于它的起点。区间[1,2]和[2,3]的边界相互“接触”，但不重叠。将思路区间按照左端点从小到大贪婪排序，然后temp_pos指针指向第i个区间。当temp_pos指针指向的区间右端点>第i区间左端点，temp_pos指针指向区间右端点>第i区间右端点时，表示当前的区间覆盖范围大于第i区间，所以可以去掉current区间，保留第i区间，更新temp_pos指针。只要temp_pos指针指向的区间右端点>第i区间左端点，计数就会+1。当当前区间的右端点<=第i个区间的左端点时，说明没有重叠，需要更新temp_pos。时间复杂度：O(len(intervals))空间复杂度：O(1)PythoncodeclassSolution(object):deferaseOverlapIntervals(self,intervals):""":typeintervals:List[List[int]]:rtype:int"""ifnotintervalsorlen(intervals)==0:return0intervals.sort(key=lambdax:x[0])#按左端点从小到大排序temp_pos=0cnt=0foriinrange(1,len(intervals)):ifintervals[temp_pos][1]>intervals[i][0]:#当当前区间的右端点>第i个区间的左端点时ifintervals[i][1]
