iii. Interval Problems

Intervals on a line produce interval graphs, which are perfect: maximum clique = chromatic number, and maximum independent set = minimum clique cover. Most of these problems fall to a sort plus a sweep.

Conventions first

Decide whether touching intervals conflict. With half-open $[s,e)$ they don’t; with closed $[s,e]$ they do. In event sweeps this becomes the tie-break: process “end” ($-1$) before “start” ($+1$) at equal times for half-open intervals. Getting it backwards fails exactly one test.

Selection

Maximum number of disjoint intervals: sort by end and take every interval that starts after the last taken end. Greedy stays ahead. Earliest start, shortest length and fewest conflicts are all wrong rules.

Why the other sort keys fail

• Earliest start — one very long interval starting first blocks everything after it.
• Shortest duration — a short interval in the middle can block two long, disjoint ones on either side.
• Fewest conflicts — plausible-sounding, but small constructible counterexamples exist.

Only earliest finish time provably stays ahead of every other schedule at every step.

sort(all(iv), [](auto& a, auto& b) { return a.second < b.second; });
int cnt = 0; ll last = LLONG_MIN;
for (auto [s, e] : iv) if (s >= last) cnt++, last = e;     // half-open

• Minimum intervals to remove so the rest are disjoint: $n-$ the above.
• Minimum points stabbing all intervals has the same answer (duality): put a point at each chosen end.

Proof: min stabbing points = max disjoint intervals

Max disjoint $\le$ min points: any stabbing point set hits every interval, and two disjoint intervals share no point, so each of the max-disjoint intervals needs a distinct stabbing point — hence min points $\ge$ max disjoint. Min points $\le$ max disjoint: the greedy max-disjoint-interval selection (sort by end, take if it starts after the last taken end) places one point per taken interval, at its end; every interval not taken was skipped because it started before the last taken end, meaning it overlaps the taken interval whose end is $\le$ its own end (by the sort order, the last taken interval ends no later than the skipped one), so that point also lies inside every such interval. Hence this set of (max disjoint count)-many points stabs everything, giving min points $\le$ max disjoint. Both inequalities give equality. $■$

• At most $k$ intervals overlapping at any point, maximise the count: sort by end, keep a multiset of the $k$ machines’ free times, assign each interval to the machine that freed latest before its start, otherwise skip it.
• On a circle: fix the interval with the earliest end that you take, then solve linearly; or double the time axis and use binary lifting on “next interval” pointers to get $O(n\log n)$ for all starting choices.
• Many queries “max disjoint intervals inside $[L,R]$”: precompute $nxt(i)$ = interval with the smallest end among those starting at or after the end of $i$. Then binary lifting answers each query in $O(\log n)$.

Weighted (maximise total value): DP over intervals sorted by end, with $p(i)$ = the last interval ending at or before $s_i$:

$d{p}_i=\max (d{p}_{i-1},v_i+d{p}_{p(i)}).$

Binary search for $p(i)$, $O(n\log n)$.

Proof: the weighted interval scheduling DP is correct

With intervals sorted by end, $d{p}_i$ is defined to be the maximum achievable value using only intervals $1,\dots ,i$. Interval $i$ either is or isn’t in the optimal solution for the prefix $1,\dots ,i$: if not, the best is $d{p}_{i-1}$; if it is, nothing with start $>p(i)$ and index $\le i-1$ can also be chosen (by definition $p(i)$ is the last interval ending at or before $s_i$, so any interval after $p(i)$ and before $i$ overlaps $i$), and nothing with index $>p(i)$ and $\le i$ needs to be excluded for other reasons since those are exactly the intervals compatible or equal to $i$ — so the best achievable while including $i$ is $v_i+d{p}_{p(i)}$ (the best over intervals compatible with $i$, which are exactly $1,\dots ,p(i)$). Taking the max of the two cases gives $d{p}_i=\max (d{p}_{i-1},v_i+d{p}_{p(i)})$, and $d{p}_n$ is the answer by definition. $■$

The DP is necessary (greedy fails) because the best choice at interval $i$ depends on the best achievable before $i$‘s start, by value or by value density — information greedy’s single forward pass never reconstructs; one huge-value interval can also simply outweigh several smaller ones it conflicts with, so greedy-by-count is wrong too.

With $k$ parallel machines: min-cost flow on the time axis (a chain with capacity $k$ and cost 0, plus an arc of capacity 1 and cost $-v_i$ from $s_i$ to $e_i$ for each interval), $O(n^2\log n)$. That modelling pattern, “intervals as arcs over a time line with capacity $k$”, is reusable.

Further variants of the weighted problem:

Variant	Method	Cost
at most $k$ intervals	add a second DP dimension, dp[i][k]	$O(nk\log n)$
intervals on a circle, weighted	fix one interval as forced-included / forced-excluded, solve linearly both ways	$O(n^2\log n)$
setup time $g$ needed between consecutive intervals	search for $p(i)$ against $s_i-g$ instead of $s_i$	$O(n\log n)$
maximise count, tie-break by weight	DP on the pair (count, weight)	$O(n\log n)$
value depends on when it’s scheduled, not just which interval	a more general DP keyed on position, not just index	problem-specific

The recurring shape — sort by one coordinate, binary search (or two-pointer) the last compatible predecessor, take the max — generalises well beyond intervals:

Problem	The “predecessor”
weighted interval scheduling	last interval finishing before this one starts
LIS with weights	last smaller element
longest chain of pairs	last compatible pair
box stacking / Russian dolls	last box this one fits inside
job sequencing with deadlines	see Scheduling
maximum sum of non-adjacent elements	index $i-2$

When the predecessor index is monotone in $i$, the binary search becomes a two-pointer, giving $O(n)$ after the sort instead of $O(n\log n)$.

Partitioning

Minimum rooms = maximum depth (number of intervals covering one point). Assign real rooms by sorting by start and reusing the room whose last interval ended earliest (a min-heap of (end, room)).

Proof: minimum rooms equals maximum depth

Lower bound. At any instant when $d$ intervals are simultaneously active, each needs its own room at that instant, so at least $d$ rooms are necessary — hence rooms $\ge$ max depth. Upper bound (the heap greedy uses at most max-depth rooms). Process intervals sorted by start; before assigning interval $i$, pop the heap’s minimum-end room if that end is $\le s_i$ (the room is free) and reuse it, else allocate a new room. Suppose this ever allocates a room beyond the $d$-th: at that moment, all $d$ existing rooms hold intervals with end $>s_i$ (else the heap’s minimum would have been popped), meaning $d$ other intervals are each still active at time $s_i$ — together with interval $i$ itself (which starts at $s_i$) that is $d+1$ intervals simultaneously active at $s_i$, contradicting that the depth never exceeds $d$. So at most $d$ rooms are ever opened, matching the lower bound. $■$

vector<pair<ll, int>> ev;
for (auto [s, e] : iv) ev.push_back({s, +1}), ev.push_back({e, -1});
sort(all(ev));                        // -1 before +1 at equal times: half-open
int cur = 0, depth = 0;
for (auto [t, d] : ev) depth = max(depth, cur += d);

• Setup gap $g$ between consecutive bookings: extend each end by $g$.
• Depth at every point: difference array over compressed coordinates.
• Which intervals contain a given query point: offline, a sweep; online, a set of currently-open intervals ordered by end, or a segment tree keyed by start.
• Rooms with capacities or types: flow, or greedy with a heap per type when the types are nested.
• CPU scheduling with $k$ cores: with fixed start and end times this is exactly minimum-rooms; once start times become flexible (choose when to run each job) it turns into a makespan problem, which is NP-hard — flexibility in timing is what breaks the interval-graph structure.

“Minimise the number of resources” and “maximise simultaneous demand” are dual, and equal, specifically because intervals form a perfect graph (clique number = chromatic number) — that equality is what makes a single sweep sufficient here. Outside interval structure the two quantities can differ and the problem usually becomes NP-hard, so spotting “this is an interval graph” is most of the insight.

Covering

Fewest intervals covering $[L,R]$: sort by start; from the current covered point, among intervals starting at or before it, take the one reaching furthest; repeat. If none extends coverage, it’s impossible. For many queries, binary lifting on “furthest reach from $x$” gives $O(\log n)$ each.

Proof: furthest-reach greedy minimises the number of intervals covering $[L,R]$

Greedy stays ahead. Let $c_0=L<c_1<c_2<\dots$ be the covered-point values after each greedy pick, and $c_0=L<c_1^{\prime }<c_2^{\prime }<\dots$ the corresponding values of any optimal solution’s partial covers, both counted after $k$ intervals. Claim $c_k\ge c_k^{\prime }$ for all $k$: by induction, assuming $c_{k-1}\ge c_{k-1}^{\prime }$, the optimal solution’s $k$-th interval starts at or before $c_{k-1}^{\prime }\le c_{k-1}$ (else it wouldn’t extend its own cover), so it is among the candidates greedy could have chosen at step $k$ (candidates: intervals starting at or before the current covered point); greedy picks the one reaching furthest among all such candidates, so $c_k\ge$ (optimal’s $k$-th interval’s reach) $=c_k^{\prime }$. Since greedy always covers at least as far as any solution after the same number of picks, if an optimal solution finishes covering $R$ in $m$ intervals, greedy has $c_m\ge c_m^{\prime }\ge R$, so greedy also finishes within $m$ intervals — greedy never needs more than the optimum. $■$

Union length / merging: sort by start and extend the current block while the next start is at most its end.

Point coverage queries: offline, sweep with a BIT over compressed endpoints; online, a segment tree or “merge sort tree on starts”.

Interval graph algorithms

Problem	Polynomial on interval graphs
maximum independent set	greedy by end
maximum clique	maximum depth (sweep)
chromatic number	maximum depth; greedy colouring in order of start
minimum clique cover	equals max independent set
maximum weight independent set	DP above
minimum dominating set	greedy
Hamiltonian path / cycle	polynomial, greedy-ish with care

General recognition and the chordal-graph extensions: Special Graph Classes.

Nesting and containment

• Count, for each interval, how many intervals it contains / is contained in: sort by $(l\uparrow ,r\downarrow )$ and count with a BIT over compressed $r$ (CSES “Nested Ranges Count”). Equal intervals contain each other, so handle duplicates with the tie order.
• Longest chain of nested intervals: sort by $l$ ascending and $r$ descending, then the longest non-increasing subsequence of $r$.

Proof: longest nesting chain = longest non-increasing subsequence of $r$ after this sort

Interval $i$ is nested inside interval $j$ (i.e. $[l_i,r_i]\subseteq [l_j,r_j]$, $i$ the inner one) iff $l_j\le l_i$ and $r_i\le r_j$. After sorting by $l$ ascending (ties broken by $r$ descending), a chain of intervals $j_1,j_2,\dots ,j_k$ nested from outermost to innermost appears as indices in increasing sort order with $l_{j_1}\le l_{j_2}\le \dots$ automatically satisfied by the sort, and the nesting condition then reduces to exactly $r_{j_1}\ge r_{j_2}\ge \cdots \ge r_{j_k}$ (non-increasing $r$) — provided no two chain members have equal $l$ with the wrong $r$ order, which the tie-break ($r$ descending among equal $l$) prevents (equal-$l$ intervals are ordered so the one with larger $r$, which nests the other, comes first, matching “outer before inner”). So a nesting chain corresponds exactly to an index-increasing, $r$-non-increasing subsequence, i.e. a non-increasing subsequence of the $r$ array in this order, and the longest one gives the longest nesting chain. $■$

• Interval containment as 2D dominance: $(l,r)$ contains $(l^{\prime },r^{\prime })$ iff $l\le l^{\prime }$ and $r^{\prime }\le r$, so these are offline 2D counting problems (Offline 2D Queries).