Intervals

An interval is a [start, end] range, and two intervals overlap exactly when each one starts before the other ends: a.start <= b.end and b.start <= a.end.

Sort intervals by start, then sweep once: each interval either extends the last merged block or starts a new one, for O(n log n) total.

To insert a new interval into a sorted, disjoint list, copy everything that ends before it, absorb everything that overlaps it, then copy the rest: one pass, O(n).

To find how many intervals are active at once, turn each interval into a +1 start event and a -1 end event, sort the events, and sweep while keeping a running count; the peak is the answer.

To keep the most non-overlapping intervals, sort by end time and greedily take each interval that starts after the last one you took; earliest finish leaves the most room for the rest.