435. 无重叠区间

题目描述

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

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

提示:

1 <= intervals.length <= 10⁵
intervals[i].length == 2
-5 * 10⁴ <= start_i < end_i <= 5 * 10⁴

解法一：动态规划（超时）

规定：dp[i] 表示以区间 i 为最后一个区间，可以选出的区间数量的最大值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


func max(nums ...int) int {
    ans := nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] > ans {
            ans = nums[i]
        }
    }
    return ans
}

func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    n := len(intervals)
    dp := make([]int, n)
    dp[0] = 1
    for i := 1; i < n; i++ {
        dp[i] = 1
        for j := 0; j < i; j++ {
            if intervals[j][1] <= intervals[i][0] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }
    return n - dp[n-1]
}

解法二：贪心

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        a, b := intervals[i], intervals[j]
        return a[0] < b[0] ||
            a[0] == b[0] && a[1] < b[1]
    })
    n := len(intervals)
    // count records the number of non-overlapping intervals
    count, prev := 1, intervals[0][1]

    for i := 1; i < n; i++ {
        if intervals[i][0] < prev {
            if intervals[i][1] < prev {
                prev = intervals[i][1]
            }
        } else {
            // intervals[i][0] >= prev
            prev = intervals[i][1]
            count++
        }
    }

    return n - count
}

官方题解如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


func eraseOverlapIntervals(intervals [][]int) int {
    n := len(intervals)
    if n == 0 {
        return 0
    }
    sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] < intervals[j][1] })
    ans, right := 1, intervals[0][1]
    for _, p := range intervals[1:] {
        if p[0] >= right {
            ans++
            right = p[1]
        }
    }
    return n - ans
}