435. Non-overlapping Intervals #

Problem #

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.

Problem Summary #

Given a collection of intervals, find the minimum number of intervals that need to be removed so that the remaining intervals do not overlap.

Note:

1. You may assume the interval’s end point is always greater than its start point.
2. The boundaries of intervals [1,2] and [2,3] “touch” each other, but they do not overlap.

Solution Ideas #

• Given a group of intervals, ask what is the minimum number of intervals to delete so that these intervals do not overlap with each other. Note that the start point of a given interval is always less than the end point. [1,2] and [2,3] are not considered overlapping.
• This problem can be considered in reverse: given a group of intervals, ask what is the maximum number of intervals that can be kept so that these intervals do not overlap with each other. Sort first, then determine whether intervals overlap.
• One approach to this problem is to use dynamic programming, imitating the idea of the longest increasing subsequence.
• Another approach to this problem is to sort by the end of the intervals, and each time choose the interval with the earliest end that does not overlap with the previous interval. Choosing the one with the earliest end leaves more space for later intervals to choose from. This allows more intervals to be kept. This approach is the idea of a greedy algorithm.

Code #

package leetcode

import (
	"sort"
)

// Solution 1 DP O(n^2) The idea is to imitate the idea of the longest increasing subsequence
func eraseOverlapIntervals(intervals [][]int) int {
	if len(intervals) == 0 {
		return 0
	}
	sort.Sort(Intervals(intervals))
	dp, res := make([]int, len(intervals)), 0
	for i := range dp {
		dp[i] = 1
	}
	for i := 1; i < len(intervals); i++ {
		for j := 0; j < i; j++ {
			if intervals[i][0] >= intervals[j][1] {
				dp[i] = max(dp[i], 1+dp[j])
			}
		}
	}
	for _, v := range dp {
		res = max(res, v)
	}
	return len(intervals) - res
}

// Intervals define
type Intervals [][]int

func (a Intervals) Len() int {
	return len(a)
}
func (a Intervals) Swap(i, j int) {
	a[i], a[j] = a[j], a[i]
}
func (a Intervals) Less(i, j int) bool {
	for k := 0; k < len(a[i]); k++ {
		if a[i][k] < a[j][k] {
			return true
		} else if a[i][k] == a[j][k] {
			continue
		} else {
			return false
		}
	}
	return true
}

// Solution 2 Greedy O(n)
func eraseOverlapIntervals1(intervals [][]int) int {
	if len(intervals) == 0 {
		return 0
	}
	sort.Sort(Intervals(intervals))
	pre, res := 0, 1

	for i := 1; i < len(intervals); i++ {
		if intervals[i][0] >= intervals[pre][1] {
			res++
			pre = i
		} else if intervals[i][1] < intervals[pre][1] {
			pre = i
		}
	}
	return len(intervals) - res
}