← Intervals · guided lesson
Intervals
the story
Interval merging (sort by start)
Every tool here exists because something was too slow or broke without it. Here is what.
A folklore technique with no single inventor: it's what any "union of ranges" code does after sorting. The HTML standard even requires browsers to keep a video's buffered ranges merged this way.
why it matters: without it
Overlapping ranges get double-counted (coverage looks bigger than it is), and every free-slot search compares every pair.
also in this chapter: Interval scheduling (earliest finish first) · Interval partitioning (rooms = maximum overlap) · Sweep line & difference array
the idea
The idea in 30 seconds
An interval is a stretch [start, end]: a meeting, a booking, a downloaded piece of a video, a balloon on the x-axis.
Almost every interval problem starts with a sort: by start to merge or sweep, by end to keep the most or to stab them with the fewest points.
After the sort, one left-to-right pass, with a variable or a min-heap of end times, gives the answer in O(n log n).
picture this
The grey buffered bar under a video. As you skip around, the browser downloads pieces as [start, end] time ranges and keeps them merged: the HTML standard says the buffered ranges must be sorted, never overlap and never touch, so touching pieces are folded into one. That is Merge Intervals, running inside every browser's video player.
watch it
Merge intervals
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Merge intervals
After sorting by start, each interval either stretches the current group or opens a new one.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Insert interval: copy, absorb, copy
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Insert interval: copy, absorb, copy
The list is already sorted, so no sort: copy what ends before, absorb what overlaps, copy what starts after.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 8
Read it once. Say it out loud once. Bas.
Overlap test for closed [a, b] and [c, d]: a <= d && c <= b. For half-open meetings [a, b): a < d && c < b. One < vs <= decides whether touching counts.
key idea 2 of 8
Read it once. Say it out loud once. Bas.
Read the touching rule every time. LC 56 merges [1,4] and [4,5]. LC 435 and meeting rooms let [1,2] and [2,3] live together. In LC 452 one arrow at x = 2 bursts both [1,2] and [2,3].
key idea 3 of 8
Read it once. Say it out loud once. Bas.
Sort by start to combine or sweep (merge, insert, meeting rooms, free time). After the sort, the next interval can only overlap the last group.
key idea 4 of 8
Read it once. Say it out loud once. Bas.
Sort by end to keep the most intervals or to stab them with the fewest points (LC 435, LC 452). The earliest finisher leaves the most room: the exchange argument from the Greedy chapter.
key idea 5 of 8
Read it once. Say it out loud once. Bas.
Rooms needed = the most intervals overlapping at one moment. Get it with a min-heap of end times, or with two sorted arrays (starts and ends).
key idea 6 of 8
Read it once. Say it out loud once. Bas.
Sweep line / difference array: +k at a start, −k at an end, then a running sum. An int[] for small coordinates, a TreeMap for huge or sparse ones.
key idea 7 of 8
Read it once. Say it out loud once. Bas.
Offline queries: when many points ask about many intervals (LC 1851), sort the queries too and sweep both together with a heap.
key idea 8 of 8
Read it once. Say it out loud once. Bas.
Comparator safety: Integer.compare(a[0], b[0]), never a[0] - b[0]. LC 452's coordinates span the whole int range.
spot the pattern
When you see this, think this
"Merge", "insert", "union of ranges"
Sort by start, extend the last group
"Maximum number of non-overlapping …", "minimum removals so nothing overlaps"
Sort by end, keep what fits (activity selection)
"Minimum rooms / platforms / cars", "max concurrent", "capacity at any time"
Min-heap of end times, sweep line, or difference array
"Minimum arrows / points to cover all intervals"
Sort by end, place the point at the earliest end
+3 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Sorting by the wrong key. Sorting by start (or by length) breaks activity selection: [1,10], [2,3], [4,5].
- Comparator overflow:
a[1] - b[1]breaks for values near ±2³¹. UseInteger.compare.
quick check
One question. No pressure.
To keep the MOST non-overlapping intervals, which sort order makes greedy correct?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Merge Intervals
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Write the overlap test for closed [a,b] and [c,d], and for half-open meetings.
Question 1: Write the overlap test for closed [a,b] and [c,d], and for half-open meetings.
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.