Intervals

6 questions, and almost all of the work is two decisions made before any code is written: which key to sort by, and whether touching counts as overlapping.

The sort key is the algorithm

Sort by	Because	Questions
start	you are building a union, and need to know what comes next	1, 2, 4, 5
end	you are choosing what to keep, and want maximum room left over	3
size	you want the best candidate, not the next one	6

One character of difference between a[0] and a[1], and it decides correctness rather than style. Measured: sorting Non-Overlapping Intervals by start instead of end gives the wrong answer on 379 of 3,000 random inputs.

Closed or half-open — ask before writing the comparison

This is the one thing you cannot infer from the problem statement, and it inverts the answer on every touching pair.

Question	Convention	Does `[1,4]` meet `[4,5]`?	The line
Insert Interval	closed	yes, merge	`a[i][0] <= new[1]`
Merge Intervals	closed	yes, merge	`a[i][0] <= cur[1]`
Non-Overlapping	boundary shared is fine	no conflict	`a[i][0] >= end`
Meeting Rooms	half-open	no conflict	`a[i][0] < a[i-1][1]`
Meeting Rooms II	half-open	room is freed	`ends[j] <= starts[i]`
Min Interval per Query	inclusive	size is `r − l + 1`	`peek()[1] < q`

The apparent inconsistency is real and it has a reason: merging asks whether the union is connected; scheduling asks whether both can happen. Different questions, opposite answers at a shared endpoint.

Sorting turns pairs into neighbours

Every O(n log n) solution here rests on the same invariant:

After sorting by start, if the next interval doesn't reach the one being built, nothing later reaches it either — so the current interval is final and can be emitted or compared against permanently.

That is what collapses C(n,2) pairwise questions into n−1 adjacent ones. It is stated three times in this section — for merging, for conflict detection, and for room counting — and it is the same sentence each time.

The `Math.max` that is only needed half the time

Merging: the new end is a max, not the latest end

Merge Intervals must write cur[1] = Math.max(cur[1], a[i][1]), because sorting by start says nothing about ends and a nested interval has a smaller one. Measured: assignment instead of max is wrong on 1,252 of 4,000 random inputs — 31%, and the output still looks like a plausible list of intervals.

Non-Overlapping Intervals writes plain assignment and is correct — because sorting by end makes the ends non-decreasing, so max and assignment coincide.

Same-looking line, different justification. Knowing which is which is the point.

Concurrency: the same sweep, three questions

Meeting Rooms II: the answer is the peak concurrency

Question	What you do with the running count
Merge Intervals	emit a segment whenever it returns to 0
Meeting Rooms	return false if it ever exceeds 1
Meeting Rooms II	return its maximum
"covered by at least k"	emit whenever it crosses k

One machine, four problems. The decoupling that makes it work — that you may sort the starts and the ends into separate arrays and lose track of which belonged to which — is the single most transferable idea in the section.

Offline processing

Answering queries offline: sort them, then sweep once

Minimum Interval to Include Each Query is Hard for one reason: you have to notice that nothing requires answering the queries in the order they were given. Sorting them makes intervals monotone in both directions — candidates are only added, expiries are permanent — and the whole problem becomes one sweep.

It also introduces lazy deletion: the interval that needs evicting isn't at the top of a size-ordered heap, and binary heaps can't delete arbitrary elements. So you evict only from the top, only when it's stale, and let the rest rot harmlessly. The same trick appears in Dijkstra and in sliding-window heaps.

Medium Insert Interval LC 57 13 min Medium Merge Intervals LC 56 13 min Medium Non-Overlapping Intervals LC 435 14 min Easy Meeting Rooms LC 252 11 min Medium Meeting Rooms II LC 253 15 min Hard Minimum Interval to Include Each Query LC 1851 15 min

Complexity

Question	Time	Space
Insert Interval	`O(n)`	`O(n)` output
Merge Intervals	`O(n log n)`	`O(n)`
Non-Overlapping Intervals	`O(n log n)`	`O(1)`
Meeting Rooms	`O(n log n)`	`O(1)`
Meeting Rooms II	`O(n log n)`	`O(n)`
Min Interval per Query	`O(n log n + q log q)`	`O(n + q)`

Everything except Insert Interval is sort-bound, and O(n log n) is optimal in the comparison model — these problems subsume element distinctness. Insert Interval escapes only because its input arrives sorted.

The traps

Trap	Symptom
Assignment instead of `Math.max` on the end (Q2)	Wrong on 1,252/4,000; `[[1,5],[2,3]]` gives `[[1,3]]`
`<` instead of `<=` in the overlap test (Q1)	Wrong on 381/4,000; `[[1,3]] + [3,5]` stays split
Sorting by start instead of end (Q3)	Wrong on 379/3,000; `[[1,10],[2,3],[4,5]]` gives 2
Sorting by length (Q3)	`[[1,5],[4,6],[5,9]]` gives 2 instead of 1
Never polling the heap (Q5)	Wrong on 2,759/4,000 — the answer degenerates to `n`
Polling the heap in a loop (Q5)	Heap size tracks current occupancy, not the peak
`<` instead of `<=` when freeing a room (Q5)	Back-to-back meetings each hold a room
Forgetting the trailing `res.add(cur)` (Q2)	Every input loses its last merged group
`right − left` instead of `right − left + 1` (Q6)	`[[4,4]]` with query 4 returns 0 instead of 1
Sorting the queries in place (Q6)	Answers land in the wrong output positions
Re-sorting an already-sorted input (Q1)	Correct, but throws away the `O(n)` solution

Verification

Every snippet compiled and cross-checked against an independent implementation — 22,000+ randomized cases:

Q1 against append-then-merge-from-scratch
Q2 against a brute force that repeatedly fuses any overlapping pair and restarts
Q3 against the maximum non-overlapping subset over all 2^n subsets
Q4 against an all-pairs overlap check
Q5 across the min-heap and the two-pointer sweep, against max concurrency sampled at every start
Q6 against scanning every interval for every query

Separately, a second harness recomputes every numeric claim in the prose and both diagram data rows, and differentially tests every alternate implementation shown in the files — the binary-search variant of Insert Interval, the sweep-line variant of Merge Intervals, the O(n²) DP for Non-Overlapping, the separated-endpoint form of Meeting Rooms, the TreeMap difference map for Meeting Rooms II, and both the TreeSet smallest-first solution and the max-heap follow-up variant for Q6. All agree on 21,000+ further cases.

One correction that came out of it: the reference implementation for Q3 originally checked overlap between sorted neighbours of a subset, which is order-dependent when starts tie. It disagreed with the greedy, and the reference was the thing that was wrong. It now checks all pairs with max(starts) < min(ends), which is order-independent.