Coding

Greedy

Make the locally optimal choice; prove it stays globally optimal.

Coding pattern

Overview

Greedy algorithms make the locally optimal choice at each step and hope it yields a global optimum. They're fast and simple, but only correct when the problem has the greedy-choice property — so the real work is proving (or disproving) that it applies.

How it works

Coding pattern

ClientServiceEdgeData

Step by step, with examples

1
Options
- Confirm a local choice is provably safe.
2
Sort by cost
- Order by cost, deadline, or value.
3
Greedy choice
- Take the best available at each step.
4
Result
- Locally optimal choices give a global optimum.
- Example: Interval scheduling

When to reach for it

Interval scheduling
Coin/change with canonical sets
Sorting then picking

Example problem

Maximum non-overlapping intervals.

Approach

Sort by end time
Greedily take each interval that starts after the last taken end

Solution

function maxIntervals(intervals) {
  intervals.sort((a,b) => a[1] - b[1]);
  let count = 0, end = -Infinity;
  for (const [s,e] of intervals)
    if (s >= end) { count++; end = e; }
  return count;
}

Complexity

Time O(n log n), Space O(1).

Common pitfalls

Greedy not always optimal — verify
Sorting on the wrong key

Where this content comes from

For full transparency, this content is curated and verified from these sources:

Curated company-tagged problem banksRecurring interview pattern librariesOppZen-authored drills & solutions