代码随想录——无重叠区间（Leetcode435）

2024/10/25 10:31:49 来源：https://blog.csdn.net/qq_46574748/article/details/140176695 浏览: 次关键词：代码随想录——无重叠区间（Leetcode435）

题目链接
在这里插入图片描述

贪心 + 排序

class Solution {public int eraseOverlapIntervals(int[][] intervals) {int res = 0;if(intervals.length == 1 || intervals.length == 0){return res;}// 按左边界排序Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] intervals1, int[] intervals2) {long diff = (long)intervals1[0] - (long)intervals2[0];if (diff == 0) return 0;return diff > 0 ? 1 : -1;}});// 记录区间分割点int end = intervals[0][1];for(int i = 1; i < intervals.length; i++){// 如果下一个点的左元素大于等于分割点，说明区间不重叠，改变区间分割点if(intervals[i][0] >= end){end = intervals[i][1];}else{// 如果下一个点的左元素小于分割点，说明区间重叠，比较区间分割点和下一个点的右元素，将区间分割点赋值为较小值end = Math.min(end,intervals[i][1]);// 移除一个区间res++;}}return res;}
}