Intervals

Tactic

Intervals model a span with a start and an end. The tactic is to stop thinking about individual points and reason about boundaries, overlap, containment, and active ranges.

The invariant usually comes from sorted starts or sorted events. Once intervals are ordered, the current interval only needs to compare against the last kept interval, the next starting boundary, or the active count.

Before coding, clarify endpoint semantics. [1, 2] and [2, 3] may overlap in one problem and not overlap in another. That single equality choice changes merge, meeting-room, and removal logic.

Value

The value is reducing many case splits to boundary comparisons. Sorting by start, end, or query value makes overlap logic local instead of pairwise.

Direct complexity example

Brute force: Check every interval against every other interval for conflicts: $O(n^2)$ time and $O(1)$ to $O(n)$ space.
With this tactic: Sort by boundary and scan, heap, or sweep events: $O(n \log n)$ time, often with $O(1)$ to $O(n)$ space.
Space: A heap or event list uses $O(n)$ space when many intervals can be active at once.

Challenges this solves

merge and insert intervals
meeting room counts
non-overlapping removals
range coverage
minimum interval for queries

When to use it

Use this tactic when these conditions are true:

items have start and end boundaries
the question asks about overlap, containment, scheduling, or coverage
ordering by start or end makes the next conflict local
endpoint inclusivity can be stated clearly

When not to use it

Reach for a different tactic when these warning signs appear:

the ranges change online and need dynamic interval structures
the problem is about arbitrary graph connectivity rather than line order
the endpoints are not comparable
the prompt needs every individual point and the range model loses information

Terminology clues

These prompt words often point toward this concept:

interval
range
start
end
overlap
meeting
schedule
cover