Non-overlapping Intervals

Medium

The problem

You get a list of ranges [start, end]. Return the smallest number of ranges you must remove so that no two remaining ranges overlap. Ranges that only touch at one point, like [1, 2] and [2, 3], do not count as overlapping.

Example 1
Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1
Remove [1, 3]. What is left, [1, 2], [2, 3], [3, 4], only touches at the ends.
Example 2
Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2
All three are identical and overlap each other, so only one can stay.
Example 3
Input: intervals = [[1, 2], [2, 3]]
Output: 0
They only touch, so nothing needs to be removed.

Limits

1 ≤ len(intervals) ≤ 100,000
start < end for every range

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

When two intervals overlap, which one is less harmful to keep?

The idea

Sort by end. Keep an interval if it starts at or after the last kept end; otherwise count a removal. (Keeping the earliest end leaves the most room.)

Target: O(n log n) time

Go function shape

func eraseOverlapIntervals(intervals [][]int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// EraseOverlapIntervals: fewest intervals to remove so the rest do not overlap.
// Greedy: sort by END, keep every interval that starts at or after the last kept end.
func EraseOverlapIntervals(intervals [][]int) int {
	sorted := slices.Clone(intervals)
	slices.SortFunc(sorted, func(a, b []int) int { return cmp.Compare(a[1], b[1]) })

	kept, end := 0, 0
	for i, iv := range sorted {
		if i == 0 || iv[0] >= end {
			kept++
			end = iv[1]
		}
	}
	return len(sorted) - kept
}

Read the lesson: Intervals