parikshan

Greedy

The core idea

A greedy algorithm makes the locally best choice at every step and commits. It runs in O(n) or O(n log n), it is short to write, and when it works it is the most beautiful kind of algorithm.

The catch: greedy only works when locally best = globally best. Proving that is half of every greedy problem. The usual proofs are by exchange ("if any optimal solution differs, I can swap one step and get something no worse") or by structural argument ("after step k, no other strategy can do better").

The first instinct of every learner is to try greedy on a DP problem and get a wrong answer that looks right. That is okay; you learn the proof discipline by failing this way once.

When to reach for it

Trigger phrases:

  • "fewest moves to ..."
  • "rearrange / partition so that ..."
  • "schedule N tasks to minimise / maximise ..."
  • "with a fixed capacity, ..."
  • "Huffman / scheduling / activity-selection" shape

Greedy is also the right reach when DP would work but is overkill (e.g., jump-game has a greedy solution in O(n) and a DP solution in O(n²)).

How to approach

  1. State the greedy choice in one sentence ("at each step, pick the item with the latest deadline").
  2. Prove it. Either by exchange argument or by induction. Don't skip this; without a proof, you have a guess.
  3. Implement. Usually a single pass after a sort.
  4. Test on the smallest case that could break it. If it survives, your proof was probably right.

Enterprise scenarios

  • AWS / Datadog autoscaling: deciding when to spin a new instance is a greedy decision over the current load forecast.
  • Uber / DoorDash dispatch: which driver picks up which order, evaluated in real time, is a greedy match against the current state.
  • CDN cache eviction: LRU is greedy over "least recently used"; LFU is greedy over "least frequently used".
  • Network routing: BGP path selection is greedy over a ranked attribute list.
  • Stripe payment retries: retry timing follows a greedy back-off; the schedule is greedy by failure history.
  • Slack message delivery: which servers fan-out the message to, given quotas.
  • Coupon and promotion systems: greedy assignment of best discount per cart item.

In the AI-integrated workspace

The agentic risk in greedy is real and consequential. An agent will write greedy code that looks elegant and ships, and the wrong answer surfaces only when the input distribution shifts. Without a proof, you do not know whether the wrong answer is coming.

Discipline for AI-generated greedy code: demand the exchange argument in the docstring. If the agent cannot produce it, the code is unverified. If the agent produces it and the argument is plausible, you check it on a 5-element worst-case example.

The second pitfall: agents sometimes pick the wrong sort key. "Sort by start time" vs. "sort by end time" gives different answers for activity selection. Verify the sort key from the proof, not from intuition.

Problems in this cluster

Medium: last-stone-weight, gas-station, partition-labels.

Start with last-stone-weight. The greedy choice (always pick the two heaviest) is so obvious that the focus shifts to the right data structure (a heap), which transfers to many other problems.