leetExpert

Module 21 · Intervals

Practice

Practice~1 min

How to practice this module

Interval drills reward sorting by the right endpoint: merge extends the current span, insert splices, arrows and meeting-rooms use an end-based greedy, and employee-free-time sweeps both schedules at once. Done when all five show Solved in the hub.

Problems

Intervals — work them in order; difficulty ascends.

0/5

solved

  1. 1Meeting RoomsEasyOverlap checkWatch for: Sort by start and compare each meeting's start with the previous end — you only need a conflict test, not rooms
  2. 2Insert IntervalMediumWalk + coalesceWatch for: Push intervals before the overlap, merge through the overlap window, then append the rest — handle full containment
  3. 3Non-overlapping IntervalsMediumEarliest-end greedyWatch for: Keep the interval that ends soonest and drop overlapping later ones; the answer is drops, not kept
  4. 4Minimum Number of Arrows to Burst BalloonsMediumSort by end + sweepWatch for: One arrow covers overlapping balloons — fire at the current end and only start a new arrow when a balloon begins after it
  5. 5Employee Free TimeHardMerged timeline sweepWatch for: Merge every employee's intervals into one sorted timeline, then the gaps between merged spans are the free time

Cheatsheet

Intervals — Sort, then sweep — merge, insert, and conflict detection.

Smell → pattern

  • Overlap / merge rangesSort by start
  • Minimum rooms / camerasSweep line events
  • Insert into sorted intervalsWalk + merge splice
  • Fewest removals for non-overlapEarliest-end greedy

Patterns

Sort + merge

Core

Smell: Collapse overlapping ranges

Sort by start. If next.start ≤ current.end, extend end; else push current and shift. Linear after sort.

sweep

Sweep events

Safe

Smell: Peak concurrent intervals

Turn intervals into +1 at start and −1 at end. Sort events; scan tracking active count.

sweep

Insert & coalesce

Reach

Smell: Add one interval into a sorted list

Copy intervals before the new one, merge through overlaps, then append the rest.

sweep

Earliest-end greedy

Careful

Smell: Max non-overlapping / min arrows

For maximum non-overlapping intervals, keep the one ending soonest and drop any later interval that overlaps it. Earliest start fails on the overlap chain.

pick527

Complexity targets

  • Merge intervals

    Time
    O(n log n)
    Space
    O(n)
    Note
    Dominated by sort

  • Sweep active count

    Time
    O(n log n)
    Space
    O(n)
    Note
    Event sort

  • Earliest-end greedy

    Time
    O(n log n)
    Space
    O(n)
    Note
    Sort by end

Traps

  • Half-open vs closed ends

    Touching endpoints may or may not overlap — read the problem. Off-by-one here fails half the cases.

  • Event sort tie-break

    When start and end share a time, decide whether ends process first. Wrong order invents a phantom overlap of 1.

  • Greedy key confusion

    Non-overlap greed sorts by END; a sort-by-start variant ‘looks sorted’ and quietly accepts overlapping chains. State the key before you code.