Greedy: Stay Ahead or Exchange

A greedy algorithm commits to the locally best choice and never revises. That is either optimal or a fast WA. The filter is a proof, not a vibe.

USACO Bronze 'Introduction to Greedy' and Silver 'Greedy with Sorting' are the same idea at two speeds. The classic is interval scheduling (CSES Movie Festival): pick the maximum number of non-overlapping intervals. Sort by end time, take an interval if it starts after the last end. Stay-ahead: at every step your solution has finished as early as any other solution with the same count, so you can always take at least as many.

Maximum non-overlapping intervals — sort by endjs

function movieFestival(intervals) {
  intervals = intervals.slice().sort((a, b) => a[1] - b[1] || a[0] - b[0]);
  let taken = 0;
  let end = -Infinity;
  for (const [l, r] of intervals) {
    if (l >= end) {
      taken++;
      end = r;
    }
  }
  return taken;
}

TRACE

Intervals [1,4], [2,3], [4,6], [3,5]. Sort by end, then take or skip.

Sort by end

Order becomes [2,3], [1,4], [3,5], [4,6].

[2,3] [1,4] [3,5] [4,6]

1 / 5

CHECK

Why does sorting intervals by start time fail for maximum count?

WA modes that look like 'greedy is wrong' but are bookkeeping:

- Closed vs open. l >= end vs l > end. Read the samples. Movie Festival treats the endpoint as free (a < b in the CSES statement: you can watch a film starting at the previous end). - Wrong key. Huffman and Kruskal have proofs. 'Take largest value first' on knapsack does not. - Forgetting a sort. Walking the input order is a different algorithm.

Density greedy on 0/1 knapsack fails; that is why Rank 4 exists. Scheduling by deadline (CSES Tasks and Deadlines) *does* sort by deadline — different theorem.

CHECK

n = 2·10⁵ intervals. You already know earliest-finish is correct. What is the complexity and the illegal cousin?

Checks 0/2

Next lesson