A change-freeze calendar stores every team’s window as it arrives. Platform files [09:00, 12:00). Ops files a nested drill [10:00, 11:00). Data files [14:00, 16:00), then a follow-up that starts the instant Data ends. “Is 10:30 frozen?” still works if you test every row. Then someone asks for a gap — a stretch with no freeze — and the finder sorts by start and subtracts consecutive ends from next starts. After the nested drill ends at 11:00, the next stored range starts at 14:00, so 11:00–14:00 looks open. It is not. Platform still covers until 12:00. The finder sorted the same span twice and treated neighboring rows as neighboring time.
That is the Merge Intervals complaint. From the Algorithms Roadmap: sort by start, then sweep once, merging when the next start is ≤ the current end. The layout is a list of ranges. The procedure collapses them into the occupied union so a gap finder or a “how much of Tuesday is frozen?” sum cannot invent a hole or double-count.
This post is only that collapse. Interval Scheduling is a later greedy job with a different output. Here we care about one messy list of [start, end) windows and the sorted sweep that makes occupancy honest.
The freeze list that lies to a gap finder
Nobody stored the overlaps on purpose. Each team posted its own window. The collection is the concatenation of those posts:
raw (as filed):
Platform [09:00, 12:00)
Nested [10:00, 11:00)
Data [14:00, 16:00)
Data+ [16:00, 17:00)A membership check can still be correct at O(n) per query. Sort does not remove the second covering of 10:00–11:00. The failure is assuming consecutive rows are consecutive occupancy:
sorted by start, gaps between neighbors (wrong):
[09:00, 12:00) then [10:00, 11:00) -> "gap" is negative, skip
[10:00, 11:00) then [14:00, 16:00) -> 11:00-14:00 looks free
[14:00, 16:00) then [16:00, 17:00) -> zero-width, skip11:00–12:00 is still frozen. Summing the four raw durations also lies: you count 10:00–11:00 twice. Sorting overlapping ranges does not make them sequential occupancy. You still have the same span stored twice.
The invariant Merge Intervals restores: after the sweep, output ranges are ordered by start, they do not overlap, and their union is exactly the union of the input. A gap between merged neighbors is a real gap.
Half-open vs closed — pick one and keep it
Java time is easiest as half-open. An Instant freeze from Monday 00:00 inclusive to Tuesday 00:00 exclusive is [start, end) in epoch millis: startMillis is in, endMillis is the first instant not in. Two adjacent days share no point, and duration is end - start with no + 1.
Closed intervals [start, end] include both endpoints. Integer ranges [1, 4] and [4, 5] share the point 4. Adjacent days stored as closed midnights would overlap on that midnight.
The merge predicate is the one the thesis named: merge when next.start ≤ current.end. What that means depends on the convention:
| Convention | Point-set overlap | Touching endpoints | This sweep |
|---|---|---|---|
Half-open [a, b) | next.start < current.end | next.start == current.end — no shared point | ≤ still merges: occupancy is contiguous |
Closed [a, b] | next.start ≤ current.end | the shared point is overlap | ≤ is required for correctness |
For a freeze calendar, merging a touch is the right occupancy: [14:00, 16:00) then [16:00, 17:00) is one busy block [14:00, 17:00). A zero-width “free” slot at 16:00 is not a slot.
Note: If two abutting half-open bookings must stay two rows for billing, use < and do not merge equals. That is a product rule, not a different algorithm. Mixing closed and half-open in one list is how you merge the wrong pairs. Pick one encoding (int minutes, long epoch millis, or Instant) and convert at the boundary.
Sort by start, then sweep once
Two steps. That is the whole procedure.
- Sort the ranges by
start(tie-break onendif you want a deterministic order; it does not change the union). - Sweep left to right. Keep one
currentrange. For eachnext, either extendcurrent.endtomax(current.end, next.end)when they overlap or touch, or emitcurrentand start a new one.
After sorting, the next start is the leftmost remaining endpoint. If it is still ≤ current.end, it belongs inside the occupancy you are already growing — maybe it sticks out past current.end, maybe it is nested and you only keep the farther end. If it is strictly after current.end, current is finished: every later start is even farther right.
You do not sort by end. An early-starting long freeze must be the one you extend. Sorting by finish would emit a nested short freeze first and fail to swallow the long tail.
Nested and chained cases are the same max on the end:
nested: current [1, 10], next [3, 4] -> still [1, 10]
chain: current [1, 5], next [4, 8] -> [1, 8]
disjoint: current [1, 5], next [7, 9] -> emit [1, 5], current = [7, 9]Empty input emits nothing. One range emits itself. Unsorted input is legal; the procedure sorts.
A walk of four windows
Same freeze list, encoded as minutes from midnight. Half-open. Merge on ≤.
input (unsorted):
[540, 720) 09:00-12:00
[840, 960) 14:00-16:00
[600, 660) 10:00-11:00
[960, 1020) 16:00-17:00
after sort by start:
[540, 720)
[600, 660)
[840, 960)
[960, 1020)
sweep:
current = [540, 720)
next = [600, 660) 600 ≤ 720 -> current = [540, max(720, 660)) = [540, 720)
next = [840, 960) 840 > 720 -> emit [540, 720); current = [840, 960)
next = [960, 1020) 960 ≤ 960 -> current = [840, max(960, 1020)) = [840, 1020)
flush current -> emit [840, 1020)
merged occupancy:
[540, 720) 09:00-12:00 nested drill swallowed
[840, 1020) 14:00-17:00 Data and Data+, touch collapsedThe real gap is 12:00–14:00 (720 to 840). A finder that walks these two rows can subtract and trust the difference. Total frozen minutes are (720 - 540) + (1020 - 840) = 360, not the 420 you would get by summing the four raw durations and double-counting 10:00–11:00.
A closed-integer walk uses the same ≤ and the same max. [1, 3], [2, 6], [8, 10], [15, 18] becomes [1, 6], [8, 10], [15, 18] — the textbook picture, one encoding away from the freeze calendar.
Java sketch
A range is two endpoints. A record is enough; Merge Intervals does not need a type hierarchy.
record Interval(int start, int end) {
Interval {
if (start > end) {
throw new IllegalArgumentException("start > end");
}
}
}Sort a mutable copy, then sweep. List.sort (Timsort on objects) is the JDK call; there is no reason to hand-roll the order.
static List<Interval> merge(List<Interval> ranges) {
if (ranges.isEmpty()) {
return List.of();
}
List<Interval> sorted = new ArrayList<>(ranges);
sorted.sort(Comparator.comparingInt(Interval::start)
.thenComparingInt(Interval::end));
List<Interval> merged = new ArrayList<>();
Interval current = sorted.get(0);
for (int i = 1; i < sorted.size(); i++) {
Interval next = sorted.get(i);
if (next.start() <= current.end()) {
current = new Interval(
current.start(),
Math.max(current.end(), next.end()));
} else {
merged.add(current);
current = next;
}
}
merged.add(current);
return merged;
}An Interval[] is the same comparator on Arrays.sort:
Arrays.sort(intervals, Comparator.comparingInt(Interval::start)
.thenComparingInt(Interval::end));After merge, “is this slot free?” is a scan (or a binary search on starts) of the collapsed list. Slot t is busy when some merged [s, e) has s ≤ t && t < e.
Note: Copying before sort is the safer default. Do not sort on every query to “make merge legal” — that is the same cargo-cult the hub names for binary search. Merge when the window set changes, then query the result. Instant windows use the same loop; !next.start().isAfter(current.end()) is start ≤ end. Epoch millis as long keeps Math.max.
Cost: the sort, then a linear pass
Time is O(n log n) from the sort, then O(n) for the sweep. Each range is visited once after the order is fixed. Space is O(n) for the output in the worst case (no overlaps) plus whatever the sort uses.
A correct merge that re-sorts on every UI keystroke is still the wrong bill; a linear scan of four raw rows can be cheaper than a merged copy you throw away. Name the hot job first, the way the Algorithms Roadmap asks.
Not Interval Scheduling
Merge Intervals keeps every occupied instant. Nested and overlapping ranges disappear as rows, not as coverage. The output can be smaller than the input; the union is the same size on the timeline.
Interval Scheduling — later in the catalog, greedy family — throws ranges away. The job is “pick a maximum subset of non-overlapping intervals,” usually by earliest finish time so the room frees soonest. You do not extend an end with max. You reject a candidate that would overlap the one you already accepted. Two meetings that overlap are not collapsed into one longer meeting; one of them loses the room.
| Job | Output | Order you sort |
|---|---|---|
| Merge Intervals | Occupied union, collapsed | By start, then sweep and extend |
| Interval Scheduling | A subset of the original ranges | Typically by earliest finish |
Do not “merge” a booking calendar when the product is one room and many candidate meetings. Collapsing [9, 12) and [11, 14) into [9, 14) invents a meeting nobody booked and hides that you still have a conflict to resolve. Scheduling’s greedy-choice argument is a different post; this one only names the fork.
If the job is “how many freezes overlap at the worst instant” (depth, not union), that is a sweep line with +1 at starts and -1 at ends, not this merge.
When not to merge this way
Skip the sort-and-sweep when the job is not “collapse a known list offline”:
- Point queries on a huge static set — millions of ranges, “does any interval contain this timestamp?” as the hot path. Merging first still leaves a list you binary-search, which is fine until updates mix with queries or you need which original ids cover the point. An interval tree (or a segment tree on compressed endpoints) is the layout for that job.
- Online inserts — a new freeze arrives every few seconds and you cannot re-sort the world. Keep a structure that stays ordered (a
TreeMapof starts to ends, merging neighbors on insert, or a balanced interval tree). Re-runningmergefrom scratch is correct at hundreds of rows; it is the wrong default at a live stream. - You must retain identity — audit wants every team’s original window, not the union. Merge for occupancy queries; keep the source rows elsewhere.
A nightly job that reads yesterday’s freeze file and writes a canonical occupancy list is exactly this algorithm. A “free/busy” API that rebuilds on every request from three ranges is a linear scan; naming Merge Intervals there is cargo-cult.
JDK: a comparator, not a MergeIntervals class
There is no java.util.MergeIntervals. The library you call is the sort:
List.sort(Comparator.comparingInt(Interval::start))on aListArrays.sort(intervals, sameComparator)on an array
Object sort is Timsort, as the hub’s JDK map already said. You are not implementing merge sort because this problem has “merge” in the title. After the list is ordered, the sweep is yours: a for loop, a current, and Math.max on the end.
Do not reach for a PriorityQueue to merge intervals. A heap would re-order by start as you go, which is a slower sort. Do not build a HashMap from start to end; duplicate starts and nested ranges make that map the wrong layout. Do not sort by end because a tutorial for Interval Scheduling used finish time.
Sort by start with the JDK comparator, then write the linear merge. That is the whole library story.
Cheat sheet
Job: collapse overlapping / touching ranges into the occupied union
Invariant: sorted by start; current is the occupancy still growing
Predicate: merge when next.start ≤ current.end (touch = merge for occupancy)
Extend: current.end = max(current.end, next.end)
Encoding: pick half-open [start, end) or closed; do not mix
Time: O(n log n) sort + O(n) sweep
Space: O(n) output (worst case: no overlaps)
Not this: Interval Scheduling (pick non-overlapping by earliest finish)
JDK: Arrays.sort / List.sort + comparator; no MergeIntervals classDo:
- Sort by start once, then sweep; emit only when the next start is strictly after
current.end. - Treat touching half-open ranges as one occupancy when the product is “busy vs free.”
- Re-merge when the window set changes, then query the collapsed list.
Don’t:
- Find gaps between consecutive raw rows after sorting and trust the subtraction.
- Sum raw durations and call it “total frozen time” while overlaps remain.
- Copy this sweep onto a room-booking conflict; that later post is Interval Scheduling.
- Re-sort on every “is this slot free?” check to make the merge feel official.
Wrap-up
Merge Intervals is an offline collapse: order the ranges by start, grow one occupancy, and emit it when the next start jumps past the current end. Half-open [start, end) with epoch millis or Instant is the encoding Java time wants; the predicate next.start ≤ current.end still merges a touch so a freeze calendar does not invent a zero-width hole. Nested ranges disappear into max on the end. The bill is the sort, then a linear pass.
That is the last search-and-scan procedure in Wave 1. Next is sorting: start with the quadratic three, then the n log n family.