网站建设j介绍ppt,棋牌app开发需要多钱,淘宝做导航网站,深圳市网站制作最好的公司一、题目描述给定一个区间的集合 intervals #xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量#xff0c;使剩余区间互不重叠 。示例 1:输入: intervals [[1,2],[2,3],[3,4],[1,3]]输出: 1解释: 移除 [1,3] 后#xff0c;剩下的区间没有重叠。…一、题目描述给定一个区间的集合 intervals 其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量使剩余区间互不重叠 。 示例 1:输入: intervals [[1,2],[2,3],[3,4],[1,3]]输出: 1解释: 移除 [1,3] 后剩下的区间没有重叠。示例 2:输入: intervals [ [1,2], [1,2], [1,2] ]输出: 2解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。示例 3:输入: intervals [ [1,2], [2,3] ]输出: 0解释: 你不需要移除任何区间因为它们已经是无重叠的了。来源力扣LeetCode链接https://leetcode.cn/problems/non-overlapping-intervals著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。二、运行结果三、解题思路这里用的是贪心策略刚好学习完贪心思想树上有一道非常类似的题活动选择。大致思想就是先将每个区间按结束时间第二列从小到大排列首先选择第一个区间然后将与其重叠的区间都移除掉统计在该区间结束后开始的第一个区间第一个不和前面的区间重叠的区间重复进行选择就可以得到最大不相交子集总区间的个数减去最大不想交子集中区间的个数就是题目所求的个数。四、AC代码class Solution {public int eraseOverlapIntervals(int[][] intervals) {//取出最大不相交子集中区间的个数总区间个数减去该数就是所求int n intervals.length;Arrays.sort(intervals, new Comparatorint[](){ //按第二列结束时间对数组排序public int compare(int[] o1, int[] o2){if(o1[1] o2[1])return o1[0]-o2[0];return o1[1] - o2[1];}});int count 1, endTime intervals[0][1]; for(int i1; in; i){if(intervals[i][0] endTime) { //开始时间在前面的结束时间之后endTime intervals[i][1];count;}}return n-count;}
}
