DSA AnimatorDSA animations
Non-Overlapping Intervals LC #435 Medium Intervals · Greedy
Problem

Given an array of intervals, return the minimum number of intervals to remove so the remaining intervals are non-overlapping.

Example
Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: Remove [1,3] — it overlaps [1,2] and [2,3]. Keep [1,2],[2,3],[3,4].
Try Examples
Approach
Greedy — Sort by End Time
Keep interval with earliest end (leaves room for more). If curr.start < prevEnd → remove current.
Intervals (Sorted by End)
Load an example to begin.
Removals 0
Variables
curr
—
prevEnd
—
Overlap?
—
Action
—
Step Logic
Press ▶ Play or Next Step to begin.
✓
Ready
0 / 0
Select an example and press Play.
Algorithm
1
Sort by end time
2
If curr.start ≥ prevEnd → keep, update prevEnd
3
Else → remove current (count++), prevEnd unchanged
Time
O(n log n)
Space
O(1)
Why Sort by End

Keeping the interval with the earliest end leaves maximum room for future intervals. When two overlap, we remove the one that ends later (current, since sorted by end).

How to solve Non-Overlapping Intervals

LeetCode 435 · Medium · Intervals · Pattern: Greedy by End

Why the obvious approach is slow

Trying every subset of intervals is exponential. Greedy works: always keep the interval that ends earliest.

The key idea

Sort the intervals by end. Keep an interval if it starts at or after the end of the last kept one. Otherwise it overlaps, so remove it, and the earlier end leaves more room for the rest.

Remember

Sort by end, and keep the one that finishes first. Removals equal n minus the most intervals you can keep.

Run the animation above on your own input, or watch the 1:13 video explanation of Non-Overlapping Intervals with a dry run and Java code.

More Intervals problems