leetExpert
Practice

Non-overlapping Intervals

Module 21 · Intervals

Problem

Given an array of intervals, return the minimum number of intervals you must remove so that the rest are non-overlapping. Touching at an endpoint ([1,2] and [2,3]) does not count as overlapping.

Examples

Example 1

Input[[1,2],[2,3],[3,4],[1,3]]Output1

Explanation. remove [1,3]; the other three are disjoint

Example 2

Input[[1,2],[1,2],[1,2]]Output2

Explanation. keep one copy of [1,2], remove the other two

Example 3

Input[[1,2],[2,3]]Output0

Explanation. touching endpoints don't overlap

Constraints

1 ≤ n ≤ 10⁵ · endpoints fit in a 32-bit integer.

Attempt it first

Reframe before you code. "Minimum removals to make the rest non-overlapping" is the same as "maximum number of intervals you can keep that are already mutually non-overlapping" — remove everything else. If you keep the largest possible non-overlapping set of size k, you remove exactly n − k. So the real problem is: pick the largest set of mutually non-overlapping intervals. That's a classic. Try to find the greedy rule before opening the hint — and be careful which endpoint you sort on.