LeetCode 435 - Non-overlapping Intervals

The problem gives an array of intervals where each interval is represented as [start, end]. Each interval describes a continuous range on a number line. The task is to remove the minimum number of intervals so that the remaining intervals no longer overlap.

leetcodemediumarraydynamic-programminggreedysorting

LeetCode Problem 435

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Greedy, Sorting

Solution

Problem Understanding

The problem gives an array of intervals where each interval is represented as [start, end]. Each interval describes a continuous range on a number line. The task is to remove the minimum number of intervals so that the remaining intervals no longer overlap.

Two intervals overlap if one starts before the other finishes. However, intervals that only touch at a boundary are considered non-overlapping. For example, [1,2] and [2,3] are valid together because the end of the first interval equals the start of the second interval.

The output is not the set of remaining intervals. Instead, we must return the minimum number of intervals that need to be removed.

The constraints are important:

  • There can be up to 10^5 intervals
  • Interval values can be negative
  • Every interval satisfies start < end

Because the input size is very large, any solution worse than approximately O(n log n) will likely time out. This immediately rules out most brute-force or quadratic dynamic programming approaches.

Several edge cases are important to recognize early:

  • Intervals that already do not overlap, the answer should be 0
  • Intervals that are all identical, we must remove all but one
  • Intervals that touch exactly at endpoints, these should not count as overlaps
  • Nested intervals such as [1,10] and [2,3], choosing the wrong interval to keep can lead to more removals later
  • Negative interval values, sorting and comparisons must still work correctly

The core challenge is deciding which interval to keep whenever an overlap occurs.

Approaches

Brute Force Approach

A brute-force solution would try every possible subset of intervals and check whether the remaining intervals are non-overlapping. Among all valid subsets, we would choose the one with the maximum number of intervals kept, then compute how many were removed.

For each subset:

  1. Check whether intervals overlap
  2. Track the largest valid subset
  3. Compute removals as n - kept

This guarantees the correct answer because every possible configuration is explored.

However, the number of subsets of n intervals is 2^n. With n up to 100000, this approach is completely infeasible.

Another possible brute-force style approach is dynamic programming with pairwise comparisons, similar to longest increasing subsequence. That approach would sort intervals and compute the maximum non-overlapping chain in O(n^2) time. Although much better than exponential time, it is still too slow for the problem constraints.

Optimal Greedy Approach

The key insight is that when intervals overlap, we should keep the interval that ends earlier.

Why does this help?

Suppose we have two overlapping intervals:

  • [1,5]
  • [2,3]

If we keep [1,5], it blocks many future intervals because it extends far to the right.

If we keep [2,3], we leave more room for future intervals.

This is a classic interval scheduling greedy strategy. By always keeping the interval with the smallest ending point, we maximize the remaining space for future intervals and therefore minimize removals.

The algorithm becomes:

  1. Sort intervals by end time
  2. Greedily keep intervals whose start is at least the previous kept interval's end
  3. Count overlaps as removals

This works efficiently in O(n log n) time because sorting dominates the runtime.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) or O(n^2) DP O(n) Explores many interval combinations
Optimal O(n log n) O(1) or O(log n) Greedy scheduling by earliest end time

Algorithm Walkthrough

  1. Sort all intervals by their ending value.

Sorting by end time is the crucial greedy step. Intervals that finish earlier are more flexible because they leave more room for future intervals. 2. Initialize a variable to track the end of the last non-overlapping interval.

After sorting, we start by keeping the first interval because it has the earliest ending point. 3. Iterate through the remaining intervals.

For each interval, compare its start value with the end value of the previously kept interval. 4. If the current interval starts before the previous interval ends, an overlap exists.

In this case, we remove the current interval. Because intervals are sorted by end time, the current interval cannot end earlier than the kept interval, so keeping the earlier-ending interval is always optimal. 5. If the current interval starts at or after the previous interval ends, the intervals do not overlap.

We keep the current interval and update the tracked end value. 6. Continue until all intervals are processed. 7. Return the number of removed intervals.

Why it works

The greedy invariant is that after processing intervals up to a certain point, we always keep the maximum possible number of non-overlapping intervals with the smallest possible ending boundary.

Choosing the interval with the earliest ending time is always safe because it leaves the most room for future intervals. Any solution that keeps a later-ending overlapping interval can be replaced with the earlier-ending one without reducing the number of intervals we can ultimately keep.

This guarantees that the greedy strategy produces the optimal solution.

Python Solution

from typing import List

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

        # Sort by ending time
        intervals.sort(key=lambda interval: interval[1])

        removals = 0

        # Keep the first interval
        previous_end = intervals[0][1]

        # Process remaining intervals
        for start, end in intervals[1:]:
            # Overlap detected
            if start < previous_end:
                removals += 1
            else:
                previous_end = end

        return removals

The implementation begins by handling the empty input case, although the constraints guarantee at least one interval. Including this check makes the function more robust.

Next, the intervals are sorted by their ending value. This ordering is what enables the greedy strategy to work correctly.

The variable previous_end stores the ending boundary of the last interval that we decided to keep. Initially, we keep the first interval because it ends earliest after sorting.

During iteration, each interval is checked against previous_end.

If start < previous_end, the intervals overlap, so we increment the removal counter.

If start >= previous_end, the intervals do not overlap, so we keep the interval and update previous_end.

Because the intervals are already sorted by end time, we never need to reconsider earlier decisions.

Go Solution

package main

import "sort"

func eraseOverlapIntervals(intervals [][]int) int {
	if len(intervals) == 0 {
		return 0
	}

	// Sort by ending time
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][1] < intervals[j][1]
	})

	removals := 0

	// Keep the first interval
	previousEnd := intervals[0][1]

	// Process remaining intervals
	for i := 1; i < len(intervals); i++ {
		start := intervals[i][0]
		end := intervals[i][1]

		// Overlap detected
		if start < previousEnd {
			removals++
		} else {
			previousEnd = end
		}
	}

	return removals
}

The Go implementation follows the same greedy logic as the Python version.

The primary difference is the use of sort.Slice to sort the intervals. Go slices are mutable, so sorting occurs in place.

Go does not require special handling for integer overflow here because the interval bounds are small relative to Go's integer range.

Unlike Python, Go does not support tuple unpacking directly in loops, so the interval values are extracted manually using indexing.

Worked Examples

Example 1

Input:

[[1,2],[2,3],[3,4],[1,3]]

After sorting by end time:

[[1,2],[2,3],[1,3],[3,4]]
Step Current Interval previous_end Overlap? Action Removals
Initial [1,2] 2 No Keep 0
1 [2,3] 2 No Keep 0
2 [1,3] 3 Yes Remove 1
3 [3,4] 3 No Keep 1

Final answer:

1

Example 2

Input:

[[1,2],[1,2],[1,2]]

After sorting:

[[1,2],[1,2],[1,2]]
Step Current Interval previous_end Overlap? Action Removals
Initial [1,2] 2 No Keep 0
1 [1,2] 2 Yes Remove 1
2 [1,2] 2 Yes Remove 2

Final answer:

2

Example 3

Input:

[[1,2],[2,3]]

After sorting:

[[1,2],[2,3]]
Step Current Interval previous_end Overlap? Action Removals
Initial [1,2] 2 No Keep 0
1 [2,3] 2 No Keep 0

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(1) or O(log n) Only constant extra variables are used, sorting may use stack space

The algorithm spends most of its time sorting the intervals by end value. The subsequent scan through the array is linear.

The greedy traversal itself uses only a few variables. Depending on the sorting implementation, additional stack space may be used internally.

Test Cases

from typing import List

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

        intervals.sort(key=lambda interval: interval[1])

        removals = 0
        previous_end = intervals[0][1]

        for start, end in intervals[1:]:
            if start < previous_end:
                removals += 1
            else:
                previous_end = end

        return removals

solution = Solution()

assert solution.eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]]) == 1
# Basic overlap example

assert solution.eraseOverlapIntervals([[1,2],[1,2],[1,2]]) == 2
# All intervals identical

assert solution.eraseOverlapIntervals([[1,2],[2,3]]) == 0
# Touching intervals are non-overlapping

assert solution.eraseOverlapIntervals([[1,100],[11,22],[1,11],[2,12]]) == 2
# Nested and overlapping intervals

assert solution.eraseOverlapIntervals([[1,5],[2,3],[3,4]]) == 1
# Greedy must prefer earlier ending interval

assert solution.eraseOverlapIntervals([[-5,-3],[-3,-1],[-2,0]]) == 1
# Negative interval values

assert solution.eraseOverlapIntervals([[1,10]]) == 0
# Single interval

assert solution.eraseOverlapIntervals([[1,2],[2,3],[3,4],[4,5]]) == 0
# Already fully non-overlapping

assert solution.eraseOverlapIntervals([[1,4],[2,5],[3,6]]) == 2
# Every interval overlaps

assert solution.eraseOverlapIntervals([[0,2],[1,3],[2,4],[3,5]]) == 2
# Alternating overlap structure
Test Why
[[1,2],[2,3],[3,4],[1,3]] Standard example with one removal
[[1,2],[1,2],[1,2]] Tests repeated identical intervals
[[1,2],[2,3]] Verifies touching endpoints are valid
[[1,100],[11,22],[1,11],[2,12]] Tests nested interval behavior
[[1,5],[2,3],[3,4]] Confirms greedy earliest-end choice
[[-5,-3],[-3,-1],[-2,0]] Ensures negative values work
[[1,10]] Smallest valid input
[[1,2],[2,3],[3,4],[4,5]] Already non-overlapping
[[1,4],[2,5],[3,6]] Heavy overlap scenario
[[0,2],[1,3],[2,4],[3,5]] Mixed overlapping chain

Edge Cases

One important edge case is intervals that touch exactly at their boundaries, such as [1,2] and [2,3]. A common bug is using <= instead of < when checking overlaps. The problem explicitly states that touching intervals are non-overlapping. The implementation correctly uses start < previous_end, which allows boundary-touching intervals to coexist.

Another important edge case is nested intervals. Consider [1,10], [2,3], and [3,4]. A naive strategy that keeps the first interval encountered would keep [1,10] and remove the other two, resulting in more removals than necessary. The greedy strategy avoids this problem by sorting by end time and always keeping the interval that finishes earliest.

A third critical edge case is when all intervals overlap completely, such as [[1,2],[1,2],[1,2]]. In this situation, only one interval can remain. The implementation correctly counts every subsequent interval as overlapping and removes all but one.

Another subtle case involves negative values, such as [[-5,-3],[-3,-1],[-2,0]]. Since the algorithm relies only on sorting and comparisons, negative numbers are handled naturally without any special logic.