LeetCode435无重叠区间

本文主要是介绍LeetCode435无重叠区间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

  给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

解析

  由于要删除尽可能少的区间 ，因此区间跨度大的一定是要先删除的，这样就有两种贪心思想了。按照区间结束的时间排序，遇到冲突直接删除，保证优先删除的结束区间是小的。或者按照区间开始时间，在删除的时候，选择删除更大结束时间的那个区间。

public static int eraseOverlapIntervals(int[][] intervals) {if (intervals.length == 0) return 0;// 按照左端点排序Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));int res = 0;int curRight = intervals[0][1];for(int i = 0; i < intervals.length - 1; i++) {if(curRight > intervals[i + 1][0]) {curRight = Math.min(intervals[i + 1][1], curRight);res++;}else {curRight = intervals[i + 1][1];}}return res;/*// 按右端点排序Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));int res = 0;int curRight = intervals[0][1];for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] < curRight) {// 有重叠，增加删除计数res++;} else {// 更新当前不重叠区间的右端点curRight = intervals[i][1];}}return res;*/}

  优化方向则是排序的过程，使用sort函数实际上是使用归并排序去进行排序，时间复杂度为O(nlogn)，如果使用基数排序，时间复杂度则是n*k，k为待排序的数的最多位数。

public int eraseOverlapIntervals(int[][] intervals) {radixSort(intervals);int count = 1;int right = intervals[0][1];for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] >= right) {count++;right = intervals[i][1];}}return intervals.length - count;}private void radixSort(int[][] intervals) {if (intervals.length < 2) {return;}int max = intervals[0][0];for (int[] row : intervals) {max = Math.max(max, row[1]);}int digit = findDigit(max);int[] counts = new int[19];int[][] sort = new int[intervals.length][2];int div = 1;for (int i = 0; i < digit; i++) {for (int[] row : intervals) {counts[(row[1] / div) % 10 + 9]++;}for (int j = 1; j < counts.length; j++) {counts[j] += counts[j - 1];}for (int j = intervals.length - 1; j >= 0; j--) {sort[--counts[(intervals[j][1] / div) % 10 + 9]] = intervals[j];}div *= 10;Arrays.fill(counts, 0);System.arraycopy(sort, 0, intervals, 0, intervals.length);}}private int findDigit(int max) {int digit = 0;for (int i = max; i > 0; i /= 10) {digit++;}return digit;}

这篇关于LeetCode435无重叠区间的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---