Non-Overlapping Intervals

Problem

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

Examples

The brute-force approach

Try every subset of intervals, check if each subset is non-overlapping, and return n minus the size of the largest non-overlapping subset.

best = 0
for subset in all_subsets(intervals):
    sorted_sub = sort(subset, by start)
    if is_non_overlapping(sorted_sub):
        best = max(best, len(subset))
return len(intervals) - best

O(2^n × n log n) — exponential. Trying all subsets is not viable.

Spotting the pattern

This is a Greedy problem. The key question to ask yourself:

When two intervals overlap, you must remove one. Which one should you keep to leave the most room for future intervals?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.