Pattern this teaches:Intervals
Non-overlapping Intervals
A medium Intervals interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Intervals
- Sheets
- 2
- Core for
- 7 roles
The problem
You are handed a list of intervals, some of which overlap. Delete as few intervals as possible so that no two of the remaining ones overlap, and return how many you deleted.
Example 1
- Input
- intervals = [[2,5],[5,7],[7,9],[2,7]]
- Output
- 1
- Why
- Dropping [2,7] leaves [2,5], [5,7], [7,9], which only touch at their ends.
Example 2
- Input
- intervals = [[3,6],[3,6],[3,6],[3,6]]
- Output
- 3
- Why
- Only one copy of [3,6] can stay, so three must go.
Constraints
- 1 <= intervals.length <= 10^4
- intervals[i].length == 2
- -5 * 10^4 <= intervals[i][0] < intervals[i][1] <= 5 * 10^4
How to think about it
Updated 2026-09-29Minimizing removals is the exact dual of maximizing how many mutually disjoint intervals can survive. The survivor that finishes earliest frees up the timeline the soonest for whoever comes next, so ordering by end coordinate guarantees you never regret keeping the first one you can grab.
Approaches, worst first
Sort by start and branch
time O(2^n) · space O(n)
Sort by start time and, upon finding a collision, branch on whether to discard the current interval or the previous one. Exploring both choices branches exponentially unless memoized, and even dynamic programming over the sorted list wastes quadratic time.
Greedy choice by end timeWrite this one
time O(n log n) · space O(1)
Sort ascending by end coordinate. Keep a pointer to the last accepted finish time; whenever the next start is strictly earlier than that finish, a collision is unavoidable and you must drop it. Otherwise, accept the interval and slide the finish pointer forward.
Where people lose marks · 3
- Sorting by start coordinate instead of end coordinate. A long interval starting early can mask multiple short, valid intervals, tricking a greedy start-based sweep into poor choices.
- Treating intervals that merely touch boundaries as overlapping. When an end matches the next start, they do not collide according to the definition and both can stay.
- Negative coordinates can break custom comparators if differences cause integer underflow; write explicit comparison checks instead of subtraction.
The theory behind it
Intervals — the ground this problem stands on. All Intervals problems
What Intervals is
An interval is a continuous range of numbers defined by two values: a start point and an end point. Think of a calendar event booked from two to four o'clock, or a cut segment on a ruler. Because each interval covers every number between its boundaries, two intervals can sit apart with empty room between them, touch at an edge, or overlap across a shared span of numbers.
When to reach for it
Reach for intervals when the input consists of start and end pairs representing time slots, schedules, ranges, or geometric segments. Phrasings asking to merge overlapping blocks, insert a new meeting into a busy calendar, find the minimum number of conference rooms needed, or count how many intervals must be removed to eliminate overlaps all point directly to interval patterns. Whenever problems involve resource contention over time, think intervals.
How the pattern works
The opening move is almost always sorting the intervals by their start times, or occasionally by their end times. Once ordered, compare the current interval with the previous one. If the new start time is less than or equal to the previous end time, the two intervals collide; merge them by stretching the previous end time to the maximum of both ends. If they do not collide, the previous interval is finished, so append it to the result and start tracking the new one. For room counts, split intervals into separate start and end events.
More Intervals problems
Target Roles
Core requirement for 7 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .