Recognizing interval problems

An interval is a pair [start, end] — a stretch of a line: a meeting time, a period, a piece of an axis. This is a short, breather section: almost everything in it starts with a single move that organizes the chaos.

As always, every pattern lesson opens with a 🎯 Try it first.

The opening move: sorting

Intervals usually arrive out of order, and it's hard to reason about them that way. The first reflex, in almost every problem in the section, is to sort — by start or by end, depending on what you want:

• Sort by start: ideal for merging and inserting (you process the intervals in the order they appear on the line).
• Sort by end: ideal for greedy choices ("how many fit without overlapping?") — keeping the ones that finish early leaves more room for the next ones.

This step costs O(n log n) and usually dominates the solution's complexity. After it, a single O(n) scan handles the rest.

The key question: do two intervals overlap?

Almost the entire section revolves around overlap. Two intervals a = [a0, a1] and b = [b0, b1] overlap when one starts before the other ends:

overlap  ⟺  a0 <= b1  AND  b0 <= a1

And the complement is useful: they do not overlap when one ends before the other begins (a1 < b0 or b1 < a0). Picture it on a line — two bars either "touch" or they don't:

[1────3]                     [1──────6]   ← overlap (they share [2,3])
     [2──────6]
                
[1──3]      [8──10]          do not overlap (3 < 8)

A detail that always raises doubts: [1,5] and [5,10] touch at the point 5. Does that count as overlap? It depends on the problem statement — sometimes the end is "open" (a meeting that ends at 5 frees the room for another that starts at 5). Always check this convention in the examples.

How to think about the section

The method is almost always the same: sort (by start or end) and do one scan comparing each interval against the accumulated "state" (the last interval in the result, or a count of overlaps). The creativity lies in choosing which endpoint to sort by and what to accumulate.

The section's problems

• Merge Intervals → sort by start + merge
• Insert Interval → insert into a sorted set
• Non-overlapping Intervals → greedy by end
• Meeting Rooms / Meeting Rooms II → event sweep

Summary

• Interval = [start, end]; think of a bar on a line.
• The first move is almost always to sort (by start to merge/insert; by end for greedy choices).
• Overlap: a0 <= b1 and b0 <= a1; watch out for the convention on touching endpoints.
• General method: sort + one scan comparing against the accumulated state.

Next lesson: the most classic problem in the section — merging intervals.