锐客网

  1. 首页 > 睿知 > it技术 > >

[LeetCode] 435. Non-overlapping Intervals

IT知识overlappingIntervals

五陵年少金市东，银鞍白马渡春风。这篇文章主要讲述[LeetCode] 435. Non-overlapping Intervals相关的知识，希望能为你提供帮助。
不重叠的区间。这题又是用到扫描线的思想。题意是给了一组intervals，求至少需要删除几个interval就能使得最后的结果集中没有重叠。
既然是找是否有重叠，那么可以根据每个interval的end对input进行排序。排序之后遍历intervals，记录不重叠的interval一共有几个（记为count），然后用intervals的总长度L - count得到最后要的结果。
时间O(nlogn)
【[LeetCode] 435. Non-overlapping Intervals】空间O(1)

1 /** 2* @param {number[][]} intervals 3* @return {number} 4*/ 5 var eraseOverlapIntervals = function(intervals) { 6// corner case 7if (intervals.length === 0) { 8return 0; 9} 10 11// normal case 12intervals = intervals.sort((a, b) => a[1] - b[1]); 13let end = intervals[0][1]; 14let count = 1; 15for (let i = 1; i < intervals.length; i++) { 16if (intervals[i][0] > = end) { 17end = intervals[i][1]; 18count++; 19} 20} 21return intervals.length - count; 22 };

 

    推荐阅读


    上一篇：Flutter-AppBar

    下一篇：淘宝APP商品搜索API提取