Non-overlapping Intervals

Free with account Updated Nov 19, 2026 · 4 min read
On this page

    Problem statement

    Given a list of intervals [start, end], return the minimum number of intervals to remove so that the remaining ones don't overlap. Intervals that only touch, such as [4, 6] and [6, 8], do not overlap.

    This is the classic activity selection problem, and it is often asked the other way round: "one meeting room, a list of meeting requests: how many meetings can you schedule?" Keeping the most is the same as removing the fewest. Original problem: LeetCode 435.

    Example

    Keeping [1,3], [4,6] and [6,8] and removing the two red meetings leaves no overlaps.
    Keeping [1,3], [4,6] and [6,8] and removing the two red meetings leaves no overlaps.
    intervals = [[1,3], [2,5], [4,6], [6,8], [5,9]]
    Output: 2          # remove [2,5] and [5,9]; 3 meetings fit in one room
    intervals = [[1,2], [2,3]]
    Output: 0          # touching is fine

    Constraints (assumed)

    • 0 ≤ n ≤ 10⁵; −5 × 10⁴ ≤ start < end ≤ 5 × 10⁴.

    What this question tests

    • Knowing (and justifying) the right greedy choice: earliest end first.
    • Seeing that "fewest removed" and "most kept" are the same problem.
    • The touching endpoints rule: ≥ versus >.

    Questions to ask first

    1. Do touching intervals overlap? (Here: no.)
    2. Return the number removed, or the number kept? (Here: removed; "max meetings" asks for kept.)
    3. Is the input sorted? (Here: no.)
    4. Do you need which intervals to remove? (Here: no; it is easy to add.)