Topic 16 of 20
Sort by start or end, then merge, insert, count overlaps or sweep over events.
Interval problems give you ranges like [start, end] and ask you to merge them, find overlaps, count how many overlap at once, or remove as few as possible. The first move is almost always to sort, either by start (for merging and inserting) or by end (for greedy selection, as in "keep the maximum number of non-overlapping intervals").
After sorting by start, two intervals [a, b] and [c, d] overlap exactly when c ≤ b. Merging is then a single pass that either extends the last merged interval or starts a new one. For "how many overlap at the same moment?" questions, use a sweep line: turn each interval into a +1 event at its start and a −1 event at its end, sort the events, and track the running count. A difference array does the same thing when coordinates are small.
Pay close attention to whether endpoints are inclusive or exclusive; that detail changes < into ≤, and interviewers watch for it. (Meeting Rooms I and II are LeetCode Premium, so this topic uses free problems that practise the same sweep-line idea.)
Total covered length with overlap handling.
The core interval problem; asked at nearly every company.
Three-phase insert: before, overlapping, after.
Classic interval scheduling: keep the earliest-ending interval.
Interval stabbing, the same greedy in disguise.
Sort by start ascending and end descending to detect covering.
Capacity check over time with a difference array.
Booking without overlap using an ordered map.
Offline queries with a heap-driven sweep.
Maintaining merged intervals as numbers stream in.