题目

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

  1. Input: [[1,2],[2,3],[3,4],[1,3]]
  2. Output: 1
  3. Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

  1. Input: [[1,2],[1,2],[1,2]]
  2. Output: 2
  3. Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

  1. Input: [[1,2],[2,3]]
  2. Output: 0
  3. Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Note:

  1. You may assume the interval’s end point is always bigger than its start point.
  2. Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

题意

给定一组区间，要求删去最少的区间，使剩余的区间互不重叠。

思路

贪心，类似于规划区间使不重叠的区间最多。先将区间按照左端点升序排序，再依次遍历，如果有两两重叠，则删去右端点较大的那个区间。

代码实现

Java

  1. class Solution {
  2.     public int eraseOverlapIntervals(int[][] intervals) {
  3.         Arrays.sort(intervals, (int[] a, int[] b) -> a[0] - b[0]);
  4.         int count = 0;
  5.         int i = 0;
  6.         for (int j = 1; j < intervals.length; j++) {
  7.             if (intervals[i][1] > intervals[j][0]) {
  8.                 count++;
  9.                 i = intervals[i][1] >= intervals[j][1] ? j : i;
  10.             } else {
  11.                 i = j;
  12.             }
  13.         }
  14.         return count;
  15.     }
  16. }

JavaScript

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