Intervals

How to think about it

Sort creates order. Then a linear scan either merges overlapping ranges or applies a greedy rule (e.g. always keep the interval that finishes first). Drawing on a line makes overlaps obvious.

Template shapes

Shape	Core move	Notes
Merge	Sort by start	Extend end if overlap
Min rooms	Sweep start/end events	Track active count
Min removals	Sort by end	Greedy keep earliest end

Complexity baseline

O(n log n) for the sort, then O(n) scan. Space O(n) for output or sort.

From template to problem

1. Normalize intervals (ensure start ≤ end).
2. Sort by the key your proof needs (start for merge, end for greedy keep).
3. Scan once, maintaining current open interval or active count.
4. Emit merged list or count conflicts.

/** Intervals template: merge overlapping ranges after sorting by start. */
export function merge(intervals: number[][]): number[][] {
  if (!intervals.length) return [];
  intervals = [...intervals].sort((a, b) => a[0]! - b[0]!);
  const out: number[][] = [[...intervals[0]!]];
  for (let i = 1; i < intervals.length; i++) {
    const cur = intervals[i]!;
    const last = out[out.length - 1]!;
    if (cur[0]! <= last[1]!) last[1] = Math.max(last[1]!, cur[1]!);
    else out.push([...cur]);
  }
  return out;
}

/** Intervals template: merge overlapping ranges after sorting by start. */
export function merge(intervals: number[][]): number[][] {
  if (!intervals.length) return [];
  intervals = [...intervals].sort((a, b) => a[0]! - b[0]!);
  const out: number[][] = [[...intervals[0]!]];
  for (let i = 1; i < intervals.length; i++) {
    const cur = intervals[i]!;
    const last = out[out.length - 1]!;
    if (cur[0]! <= last[1]!) last[1] = Math.max(last[1]!, cur[1]!);
    else out.push([...cur]);
  }
  return out;
}