35. 無重疊區(qū)間

給定一個(gè)區(qū)間的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊 。

答案

按區(qū)間的結(jié)尾進(jìn)行排序，每次選擇結(jié)尾最小，并且和前一個(gè)區(qū)間不重疊的區(qū)間。

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] a, int[] b) {return a[1] != b[1] ? a[1] - b[1] : a[0] - b[0];}});int[] t = intervals[0];int len = intervals.length;int res = 1;for (int i = 1; i < len; i++) {if (intervals[i][0] >= t[1]) {t= intervals[i];res++;}}return len - res;} }

總結(jié)

以上是生活随笔為你收集整理的35. 无重叠区间的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。