435. Non-overlapping Intervals

LeetCode 435. Non-overlapping Intervals

Description

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Constraints:

• 1 <= intervals.length <= 2 * 10^4

• intervals[i].length == 2

• -2 * 10^4 <= starti < endi <= 2 * 10^4

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.

Tags

Greedy, Sort

Solution

Finding the minimum number of intervals to be removed is equivalent to keeping as many non-overlapping intervals as possible. Thus, our greedy strategy is to preferably retain the non-intersecting invervals with smaller right interval.

To implement this, we firstly sort the given invervals by the right interval of each in ascending order. Then, compare each interval with its previous retained interval. If there is an overlap between the two intervals, the current one should be discarded, and the result will be increased by 1. Otherwise, we update the previous interval with the current one.

Complexity

• Time complexity: $O(n\log(n))$, depending on the sort algorithm;

• Space complexity: $O(\log(n))$, depending on the sort algorithm.

Code

func eraseOverlapIntervals(intervals [][]int) int {
	if len(intervals) < 2 {
		return 0
	}
	var ans int
	sort.Slice(intervals, func(i, j int) bool { // sort by the end of each interval
		return intervals[i][1] < intervals[j][1]
	})
	for preEnd, i := intervals[0][1], 1; i < len(intervals); i++ {
		if preEnd > intervals[i][0] { // overlapped, remove the current interval
			ans++
		} else { // non-overlapped, update last end
			preEnd = intervals[i][1]
		}
	}
	return ans
}

Reference

1. LeetCode 101