Non-overlapping Intervals

Explanation & Solution

Description

Given an array of intervals intervals where intervals[i] = [startᵢ, endᵢ], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Intervals that only touch at a point (e.g., [1, 2] and [2, 3]) are not considered overlapping.

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]

Output: 1

Explanation: Remove [1,3] and the remaining intervals [[1,2],[2,3],[3,4]] are non-overlapping.

Constraints

1 <= intervals.length <= 10⁵
intervals[i].length == 2
-5 * 10⁴ <= startᵢ < endᵢ <= 5 * 10⁴

Approach

Intervals pattern

1. Sort Intervals by End Time

Sort the intervals in ascending order of their end values
This is the foundation of the greedy strategy: by considering intervals that end earliest first, we leave the most room for subsequent intervals

2. Initialize Tracking Variables

Set removals = 0 to count how many intervals must be removed
Set prevEnd to the end of the first interval — this represents the end of the last interval we chose to keep

3. Iterate Through Remaining Intervals

For each interval [start, end] starting from the second one, compare its start with prevEnd

4. If start < prevEnd — Overlap Detected

The current interval overlaps with the last kept interval
Remove the current interval by incrementing removals
Do not update prevEnd — the previously kept interval already has an earlier (or equal) end time, so keeping it is optimal

5. If start >= prevEnd — No Overlap

The current interval does not overlap (touching endpoints like [1,2] and [2,3] are allowed)
Keep this interval: update prevEnd = end

6. Return the Result

After processing all intervals, removals holds the minimum number of intervals that must be removed
Return removals

Key Insight

The greedy choice of always keeping the interval with the earliest end time is optimal because it minimizes the chance of future overlaps. When two intervals overlap, the one that ends later is more likely to conflict with upcoming intervals, so discarding it and keeping the earlier-ending one always leads to the fewest total removals. This is equivalent to the classic activity selection problem.

Time

O(n log n)dominated by the sort step

Space

O(1)only a counter and one tracking variable are used (ignoring sort space)

Visualization

Input:

Interval Timeline[[1,2], [2,3], [3,4], [1,3]]

—

Press play to start visualization

CurrentCompareOverlapMerged

9 steps

Solution Code

Interval List Intersections

Meeting Rooms II