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

陪她去流浪 桃子 2019年03月15日 编辑 阅读次数：1471

题目

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是当前最小的，那么，留给后续区间的空间越大。既而，能选择的区间数就更多。

代码

 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

/**
 * 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
}

标签：算法 · LeetCode · 贪心算法

相关文章