Coding interview pattern
Make the locally optimal choice at each step when it provably yields the global optimum.
The idea
A greedy algorithm builds a solution by always taking the choice that looks best right now, never reconsidering. This is dramatically simpler and faster than DP or search, but it is only correct when the problem has the greedy-choice property: a locally optimal pick is always part of some globally optimal solution. The whole challenge is proving (or convincing yourself) that the property holds, because a greedy that looks right but is wrong fails on adversarial inputs.
The most reliable signals that greedy works are interval and scheduling problems and problems with a clear sort-then-sweep structure. Interval scheduling (maximise non-overlapping meetings) is solved by sorting on end time and greedily taking each compatible interval. Jump-game reachability, gas-station circuits, and many assignment problems also yield to a single greedy pass once you find the right ordering.
In an interview, justify the greedy with an exchange argument: assume an optimal solution differs from the greedy choice, then show you can swap in the greedy choice without making the solution worse, which means the greedy choice is safe. If you cannot construct that argument, be suspicious; the problem may actually need DP. State this reasoning explicitly, because choosing greedy without justification is a common way to get a correct-looking but unconvincing answer.
Recognition
Cost
| Operation | Time | Space |
|---|---|---|
| Sort then sweep | O(n log n) | O(1) or O(n) |
| Single linear pass (already ordered) | O(n) | O(1) |
| Heap-assisted greedy | O(n log n) | O(n) |
Worked example
Translatable skeleton
Language-agnostic on purpose. Translate it to your language of choice.
sort by key; best = init; for item in sorted: if compatible(item, best): take(item); update(best)Practice
Work these in order, easy to hard. Each is chosen to drill a different facet of the pattern.
| Problem | Level | Why it fits |
|---|---|---|
| Best Time to Buy and Sell Stock | Easy | Track the min price; greedily bank each gain. |
| Jump Game | Medium | Track the farthest reachable index. |
| Non-overlapping Intervals | Medium | Sort by end, keep the earliest finisher. |
| Gas Station | Medium | Single pass with a running tank and a reset point. |
| Partition Labels | Medium | Extend the partition to each char's last index. |
| Task Scheduler | Medium | Greedily schedule the most frequent task first. |
Avoid these
In the interview
Recognising the pattern is half the score; saying the right things out loud is the other half. These are the sentences that earn the signal.
Before committing to greedy, give the exchange argument out loud, assume an optimal solution differs from your choice and show you can swap your choice in without making it worse; that proof is the difference between a lucky answer and a correct one.
Name the sort key and why it is the right one, for example sort by end time so the earliest finisher leaves the most room; the wrong key silently breaks correctness.
If you cannot construct the exchange argument, say so and consider DP instead; flagging the uncertainty is better than asserting a greedy that fails on adversarial input.
greedy algorithm interview - interval scheduling greedy - exchange argument
Last reviewed by the site editor: June 2026
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Next up
Real problems rarely match a single pattern. Interviewers like to combine this one with these.
Track a contiguous subarray or substring without re-scanning it from scratch.
Walk two indices toward or alongside each other to avoid a nested loop.
Halve the search space each step over any monotonic condition, not just sorted arrays.
Solve overlapping subproblems once, store the results, and build the answer up.
See all coding patterns, the coding questions for your role, and the behavioral round.