[LeetCode] 435. Non-overlapping Intervals 不重叠的区间

题目

435. Non-overlapping Intervals

题意

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:

  • You may assume the interval's end point is always bigger than its start point.
  • 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.

思路

要找到最少需要移除多少个区间,找到不重叠区间最长可以是多少即可。

如果构成一个不重叠区间的最后一个区间的end是当前最小的,那么,留给后续区间的空间越大。既而,能选择的区间数就更多。

代码

/**
 * Definition for an interval.
 * type Interval struct {
 *       Start int
 *       End   int
 * }
 */
func eraseOverlapIntervals(intervals []Interval) int {
    if len(intervals) <= 0 {
        return 0
    }
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i].End < intervals[j].End
    })
    count := 1
    end := intervals[0].End
    for i:=1; i < len(intervals); i++ {
        if intervals[i].Start < end {
            continue
        }
        end = intervals[i].End
        count++
    }
    return len(intervals) - count
}

如果文章有帮助到你,请我喝杯冰可乐吧~

发表于:2019年3月15日 ,阅读量:141 ,标签:算法 · LeetCode · 贪心算法