Skip to content

Topic 16 of 20

Intervals

Sort by start or end, then merge, insert, count overlaps or sweep over events.

12 problems2 Easy8 Medium2 Hard

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. 1

    Turning runs of numbers into intervals, the reverse of merging.

  2. 2

    Total covered length with overlap handling.

    Interval Union LengthReported at: Salesforce
  3. 3

    The core interval problem; asked at nearly every company.

    Sort + MergeReported at: MetaAmazonGoogle+18
  4. 4

    Three-phase insert: before, overlapping, after.

    Insert into Sorted IntervalsReported at: GoogleAmazonMeta+1
  5. 5

    Classic interval scheduling: keep the earliest-ending interval.

    Sort by End (Greedy)Reported at: MetaAmazonMicrosoft
  6. 6

    Interval stabbing, the same greedy in disguise.

    Sort by End (Greedy)Reported at: GoogleMetaGoldman Sachs
  7. 7

    Intersecting two sorted interval lists.

  8. 8

    Sort by start ascending and end descending to detect covering.

  9. 9

    Capacity check over time with a difference array.

    Sweep Line / Difference ArrayReported at: AmazonGoogleMicrosoft+4
  10. 10

    Booking without overlap using an ordered map.

    Ordered Map of IntervalsReported at: AmazonGoogleUber
  11. 11

    Offline queries with a heap-driven sweep.

  12. 12

    Maintaining merged intervals as numbers stream in.

    Ordered Map of IntervalsReported at: Microsoft