435. 无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

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

  1. //动规，时间On^2,空间On，==和300题解法一致
  2. func eraseOverlapIntervals(intervals [][]int) int {
  3.     n := len(intervals)
  4.     if n == 0 {
  5.         return 0
  6.     }
  7.     sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
  8.     dp := make([]int, n)
  9.     for i := range dp {
  10.         dp[i] = 1
  11.     }
  12.     for i := 1; i < n; i++ {
  13.         for j := 0; j < i; j++ {
  14.             if intervals[j][1] <= intervals[i][0] {
  15.                 dp[i] = max(dp[i], dp[j]+1)
  16.             }
  17.         }
  18.     }
  19.     return n - max(dp...)
  20. }
  22. func max(a ...int) int {
  23.     res := a[0]
  24.     for _, v := range a[1:] {
  25.         if v > res {
  26.             res = v
  27.         }
  28.     }
  29.     return res
  30. }
//贪心思路，时空都是nlogn
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
}