Topic 16 of 20
Intervals
Sort by start or end, then merge, insert, count overlaps or sweep over events.
The concept
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.)
Patterns you will learn
Problems, in order
- 1
- 2Teemo AttackingEasy
Total covered length with overlap handling.
Interval Union LengthReported at: Salesforce - 3Merge IntervalsMedium
The core interval problem; asked at nearly every company.
Sort + MergeReported at: MetaAmazonGoogle+18 - 4Insert IntervalMedium
Three-phase insert: before, overlapping, after.
Insert into Sorted IntervalsReported at: GoogleAmazonMeta+1 - 5
Classic interval scheduling: keep the earliest-ending interval.
Sort by End (Greedy)Reported at: MetaAmazonMicrosoft - 6
Interval stabbing, the same greedy in disguise.
Sort by End (Greedy)Reported at: GoogleMetaGoldman Sachs - 7
- 8Remove Covered IntervalsMedium
Sort by start ascending and end descending to detect covering.
- 9Car PoolingMedium
Capacity check over time with a difference array.
Sweep Line / Difference ArrayReported at: AmazonGoogleMicrosoft+4 - 10My Calendar IMedium
Booking without overlap using an ordered map.
Ordered Map of IntervalsReported at: AmazonGoogleUber - 11
Offline queries with a heap-driven sweep.
- 12
Maintaining merged intervals as numbers stream in.
Ordered Map of IntervalsReported at: Microsoft