題目

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals 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.

Example 1:

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

Example 2:

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

Example 3:

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

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

解法思路（一）

關于排列與組合

• 排列和組合都是從給定的序列中，選幾個元素；
• 選的元素的個數(shù)不能大于序列的長度；
• 排列對選出的元素的位置有要求，比如選出 3 個元素，3 個元素的相對位置的不同，是不同的排列；
• 組合對選出的元素的位置沒有要求，比如選出 3 個元素，3 個元素的相對位置的不同，是相同的排列；
• 排列的遞歸樹中，當前層選中了一個元素，下一層元素在剩余的元素中選；
• 組合的遞歸樹中，當前層選中了一個元素，下一層元素在上一層選中的元素之后的元素中選；

暴力解法怎么解？

• 找出一組區(qū)間的所有組合，判斷每個組合是否重疊，在不重疊的組合中，找出區(qū)間最多的組合，其包含的區(qū)間的個數(shù) m，用給出的區(qū)間序列的長度 n 減去 m 得解；
• 時間復雜度是：O(2ⁿ * n)；

為什么是組合不是排列？

• 比如給定的區(qū)間序列是 [1,2], [3,4], [5,6]，排列 [1,2], [3,4] 和 [3,4], [1,2] 都是去掉了區(qū)間 [5,6] 后得到的排列，不同的排列在這道題的場景下沒有區(qū)別，所以，這里用組合而不是排列；

如何判斷一組區(qū)間是否重疊？

• 先將一組區(qū)間排序；
• 然后后面的區(qū)間的左邊界是否大于等于前一個區(qū)間的右邊界；

如何將一組區(qū)間排序？

• 對區(qū)間的起始點進行排序；
• 如果區(qū)間的起始點相等，用區(qū)間的終止點排序；

動態(tài)規(guī)劃的狀態(tài)如何定義？

• memo[i] 表示使用 intervals[0...i] 的區(qū)間能構成的最長不重疊區(qū)間序列的長度；

解法實現(xiàn)（一）

代碼實現(xiàn)

• 注意看二維數(shù)組是怎么比較的，通過自定義比較器；
• 注意 memo 的語義，是能構成的最大不重疊區(qū)間的長度，不是要刪除的區(qū)間的個數(shù)，相應的返回值是 intervals.length - res;

package leetcode._435;

import java.util.Arrays;
import java.util.Comparator;

public class Solution435_1 {

    public int eraseOverlapIntervals(int[][] intervals) {

        if (intervals.length == 0)
            return 0;

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) {
                    return o1[0] - o2[0];
                }
                return o1[1] - o2[1];
            }
        });

        // 動態(tài)規(guī)劃的狀態(tài)定義：
        // memo[i] 表示使用 intervals[0...i] 的區(qū)間能構成的最長不重疊區(qū)間序列的長度；
        int[] memo = new int[intervals.length];
        Arrays.fill(memo, 1);

        for (int i = 1; i < intervals.length; i++)
            for (int j = 0; j < i; j++)
                if (intervals[i][0] >= intervals[j][1])
                    memo[i] = Math.max(memo[i], 1 + memo[j]);

        int res = 0;
        for(int i = 0; i < memo.length; i++)
            res = Math.max(res, memo[i]);

        return intervals.length - res;
    }

    public static void main(String[] args) {

//        int [][] intervals = {{1, 2}, {4, 5}, {7, 9}};
        int [][] intervals = {{1, 2}};

        Solution435_1 s = new Solution435_1();
        int res = s.eraseOverlapIntervals(intervals);

        System.out.println(res);
    }

}

返回 LeetCode [Java] 目錄