important mid · part of Skills & Topics · Senior SWE Roadmap · related: Dynamic Programming · Sorting & Searching Algorithms · Arrays & Strings · Heaps & Priority Queues
Why this matters / recognition signals
A greedy algorithm builds a solution one step at a time, always taking the choice that looks best right now, and never reconsiders that choice later. It’s the cheapest possible strategy when it works — O(n log n) sort-then-scan instead of exponential search or a DP table — but it only produces the correct (globally optimal) answer when the problem has the greedy-choice property: a locally optimal choice at each step is provably part of some globally optimal solution, so committing to it never forecloses a better overall answer.
Recognition signals — reach for greedy when the problem says:
- “maximize/minimize the number of X selected” from a set of intervals, jobs, or items, where selections don’t need to be reconsidered once made
- “schedule as many non-overlapping…” → sort by end time, pick greedily
- “minimum number of jumps/refuels/coins” where a provably-safe local rule exists (e.g. “always jump as far as reachable”)
- The problem feels like it should need trying-all-combinations, but a sort followed by one linear pass turns out to always give the right answer
The trap: greedy and DP often apply to problems that look identical on the surface. The only way to tell them apart is to actually try to prove (or disprove) the greedy-choice property — guessing is how greedy solutions ship with silent wrong answers on some inputs.
Greedy vs DP: the classic interview trap
Fractional knapsack (you may take any fraction of an item) is greedy: sort items by value/weight ratio, take as much of the best-ratio item as fits, then move to the next-best ratio, and so on until the knapsack is full. This is provably optimal — if you ever left room by not fully taking the best-ratio item available, swapping in more of it strictly improves the solution, so the greedy choice can never be wrong.
0/1 knapsack (each item is all-or-nothing) is not greedy — it needs DP (see Dynamic Programming). The greedy-choice property breaks because taking the best-ratio item first can leave a small amount of leftover capacity that no remaining item fits, wasting it — while a different, “locally worse” first choice might have left exactly the right leftover capacity for a better combination later. The choice at step 1 can be invalidated by information only available after seeing all items, which is precisely the “overlapping subproblems, need to keep all options open” signature that DP solves and greedy cannot.
flowchart TD Q["Can I take a fraction of an item?"] -->|yes| Frac["Fractional knapsack: greedy-choice property HOLDS sort by value/weight, take greedily O(n log n)"] Q -->|no, all-or-nothing| Item["0/1 knapsack: greedy-choice property FAILS local best-ratio pick can strand capacity needs DP, O(n × capacity)"] style Frac fill:#5a3,color:#000 style Item fill:#e94,color:#000
Concrete counterexample proving 0/1 knapsack breaks greedy: capacity = 50, items (weight, value): A(10, 60), B(20, 100), C(30, 120). Greedy by ratio picks A (ratio 6.0) then B (ratio 5.0) — total weight 30, value 160, 20 capacity left over but C (weight 30) doesn’t fit. The actual optimum is B + C = weight 50, value 220. Greedy’s “obviously best” first pick locked in a combination that DP, which considers all subsets via its table, correctly avoids.
Core mechanism: activity/interval scheduling
Given a set of intervals (start, end), select the maximum number of non-overlapping intervals. The greedy rule: sort by end time, then repeatedly take the next interval whose start is >= the end time of the last taken interval.
Why end time, not start time or duration: taking the interval that finishes earliest leaves the most remaining room on the timeline for everything after it — any other valid first choice finishes no earlier, so it can only leave equal or less room. That’s the proof sketch for the greedy-choice property here: the earliest-finishing choice is never worse than any alternative.
flowchart LR subgraph Timeline["intervals sorted by end time"] direction LR I1["A: (1,3)"] --- I2["B: (2,4)"] --- I3["C: (3,6)"] --- I4["D: (5,7)"] --- I5["E: (6,8)"] end Note["pick A (ends 3) → B starts 2, overlaps, skip C starts 3, ok, pick → D starts 5, overlaps, skip E starts 6, ok, pick result: A, C, E"]
Worked trace
Intervals given as (start, end): B(2,4), A(1,3), D(5,7), C(3,6), E(6,8). Sort by end time first:
| Step | Sorted order | Interval | start >= lastEnd? | Action | lastEnd after |
|---|---|---|---|---|---|
| 0 | — | — | — | initialize | -infinity |
| 1 | A(1,3) | (1,3) | 1 >= -inf → yes | take A | 3 |
| 2 | B(2,4) | (2,4) | 2 >= 3 → no | skip B | 3 |
| 3 | C(3,6) | (3,6) | 3 >= 3 → yes | take C | 6 |
| 4 | D(5,7) | (5,7) | 5 >= 6 → no | skip D | 6 |
| 5 | E(6,8) | (6,8) | 6 >= 6 → yes | take E | 8 |
Result: {A, C, E} — 3 non-overlapping intervals, which is the maximum possible for this set. Sorting is the one-time O(n log n) cost; the scan afterward is a single O(n) pass with no backtracking.
Second mechanism: Jump Game (greedy reachability)
Given an array where nums[i] is the max jump length from index i, determine if you can reach the last index. Greedy rule: track the farthest index reachable so far; if the current index ever exceeds that farthest-reachable mark, it’s unreachable and the answer is false.
flowchart LR subgraph Arr["[2, 3, 1, 1, 4]"] direction LR A0["idx0: 2"] --- A1["idx1: 3"] --- A2["idx2: 1"] --- A3["idx3: 1"] --- A4["idx4: 4"] end Note2["farthest starts at 0 idx0: farthest = max(0, 0+2) = 2 idx1: farthest = max(2, 1+3) = 4 (already reaches end)"]
| i | nums[i] | i ⇐ farthest? | farthest before | i + nums[i] | farthest after |
|---|---|---|---|---|---|
| 0 | 2 | 0 ⇐ 0 yes | 0 | 2 | 2 |
| 1 | 3 | 1 ⇐ 2 yes | 2 | 4 | 4 |
| 2 | 1 | 2 ⇐ 4 yes | 4 | 3 | 4 |
| 3 | 1 | 3 ⇐ 4 yes | 4 | 4 | 4 |
| 4 | 4 | 4 ⇐ 4 yes | 4 | 8 | 8 — last index reached |
The greedy insight: you never need to know which earlier jump gets you the farthest, only the single number “farthest reachable so far” — collapsing what looks like a combinatorial choice (which jump length to use at each step) into one running maximum.
Third mechanism, briefly: Gas Station (running-deficit tracking)
A third distinct flavor of greedy, worth recognizing as its own shape: given gas[i] (fuel available at station i) and cost[i] (fuel needed to reach station i+1), find the starting station from which a full clockwise circuit is possible, if one exists.
The greedy insight here is different from both sorting (interval scheduling) and running-max reachability (Jump Game): if the tank ever goes negative starting from candidate station start, none of the stations between start and the station where it went negative can be a valid start either — because arriving at any of them from start already means arriving with a non-negative tank, which is only worse than starting there directly. So the moment the running tank dips below zero, jump the candidate start straight past the failure point, reset the tank to zero, and keep scanning — one linear pass, no backtracking to intermediate candidates ever needed. (A solution is guaranteed to exist, and this scan is guaranteed to find it, exactly when sum(gas) >= sum(cost) overall.)
Java — interval scheduling and jump game
import java.util.Arrays;
import java.util.Comparator;
public class GreedyExamples {
// Activity/interval scheduling: max number of non-overlapping intervals.
public int maxNonOverlappingIntervals(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(iv -> iv[1])); // sort by end time
int count = 0;
int lastEnd = Integer.MIN_VALUE;
for (int[] interval : intervals) {
if (interval[0] >= lastEnd) { // no overlap with last taken interval
count++;
lastEnd = interval[1];
}
}
return count;
}
// Jump Game: can we reach the last index?
public boolean canJump(int[] nums) {
int farthest = 0;
for (int i = 0; i < nums.length; i++) {
if (i > farthest) {
return false; // this index is unreachable
}
farthest = Math.max(farthest, i + nums[i]);
}
return true;
}
}Python — interval scheduling and jump game
def max_non_overlapping_intervals(intervals: list[tuple[int, int]]) -> int:
intervals_sorted = sorted(intervals, key=lambda iv: iv[1]) # sort by end time
count = 0
last_end = float("-inf")
for start, end in intervals_sorted:
if start >= last_end: # no overlap with last taken interval
count += 1
last_end = end
return count
def can_jump(nums: list[int]) -> bool:
farthest = 0
for i, n in enumerate(nums):
if i > farthest:
return False # this index is unreachable
farthest = max(farthest, i + n)
return TrueProving a greedy choice: the exchange argument
Since “it feels right” isn’t a proof, it helps to have one concrete proof pattern ready to apply (or attempt and fail) under interview pressure: the exchange argument.
- Assume some optimal solution
S*exists that does not make the greedy choice at the first point of difference. - Construct
S'by swapping in the greedy choice at that point, keeping everything else inS*unchanged as much as possible. - Show
S'is still valid (satisfies all constraints) and is no worse thanS*(same or better objective value). - Conclude: since
S'is at least as good as an assumed-optimalS*, the greedy choice is safe — it’s always part of some optimal solution.
Applied to interval scheduling: suppose an optimal solution S* picks some interval X as its first interval, and X doesn’t have the earliest end time — call the earliest-ending interval E. Since E ends no later than X, swapping E in for X can’t break any constraint that X satisfied (anything compatible with “starts after X ends” is also compatible with “starts after E ends,” because E ends earlier or at the same time) — so S' (with E swapped in) is still valid and has the same count. That’s the proof: the greedy choice is never strictly worse, so it’s safe to commit to it and never reconsider.
This is also exactly why the argument fails for 0/1 knapsack: swapping in the best-ratio item isn’t guaranteed to preserve validity (there’s a hard capacity constraint, not just an ordering constraint), and the counterexample earlier shows the swap can make the solution strictly worse, not just neutral.
Other classic greedy algorithms worth naming
These come up as building blocks in graph and string problems rather than as standalone interview questions, but recognizing that they’re greedy (and why) is a strong signal in a system design or advanced-algorithms conversation:
- Kruskal’s / Prim’s (Minimum Spanning Tree): greedily add the cheapest edge that doesn’t create a cycle (Kruskal) or the cheapest edge that extends the current tree (Prim) — see Graphs — Union-Find & MST. The greedy-choice property holds because of the “cut property”: the minimum-weight edge crossing any cut of the graph is always safe to include in some MST.
- Dijkstra’s shortest path: greedily finalizes the closest unvisited node at each step — see Graphs — Shortest Path. Requires non-negative edge weights for the greedy-choice property to hold; with negative weights, a “finalized” shortest distance can later be beaten by a path through an edge not yet considered, which is exactly why Dijkstra breaks and Bellman-Ford (a DP-style relaxation approach) is needed instead.
- Huffman coding: greedily merges the two lowest-frequency nodes at each step to build an optimal prefix-free binary encoding tree — a min-heap (see Heaps & Priority Queues) is the natural data structure since “two smallest” is repeatedly queried.
Noticing the common thread across all of these — and Dijkstra’s negative-weight failure mode specifically — reinforces the same lesson as fractional-vs-0/1 knapsack: greedy’s correctness is never free, it always rides on a specific structural property of the problem (a cut property, a non-negative-weight assumption, an exchange argument that holds), and that property is exactly what to check before trusting a greedy instinct on a new problem.
Complexity comparison
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force (try all subsets/orderings) | O(2^n) or O(n!) | O(n) | No pruning — considers every combination even after greedy-choice property would justify skipping most |
| Greedy (sort + single pass) | O(n log n) | O(1) extra (excluding sort) | One sort, then O(n) linear scan with no backtracking |
| Greedy (single pass, no sort needed — e.g. Jump Game) | O(n) | O(1) | Reachability is monotonic, no ordering step required |
| DP fallback (when greedy-choice property fails, e.g. 0/1 knapsack) | O(n × W) or worse | O(n × W) or reducible | Must keep all viable partial solutions, not just one running “best so far” |
Common pitfalls
- Assuming greedy works without proving it: the single most common interview mistake — a locally-optimal rule that “feels right” but has a counterexample (0/1 knapsack is the standard one to know cold). Always sanity-check with a small adversarial example before committing to greedy in an interview.
- Sorting by the wrong key: interval scheduling sorted by start time or duration instead of end time gives wrong answers on inputs where a short-but-late interval blocks more future intervals than a longer-but-earlier one would. End time is the one sort key with a clean optimality proof for “maximum count.”
- Forgetting ties need a secondary rule: when two intervals share the same end time (or two items share the same ratio), the choice between them can matter for some greedy variants (e.g. weighted variants) — plain interval-count scheduling is ties-safe, but don’t assume every greedy problem is.
- Confusing “greedy gives a valid answer” with “greedy gives the optimal answer”: a greedy pass almost always terminates and produces some result — the danger is that it’s syntactically fine and silently suboptimal, unlike a crash, which makes greedy bugs easy to ship unnoticed.
- Applying greedy reachability logic (Jump Game) to a problem that also needs the actual path, not just feasibility: tracking only
farthestdiscards which jumps were taken — if the follow-up asks for the minimum number of jumps or the actual sequence, the greedy rule needs an extra “current window end” variable to count jumps in batches, not just a single running max.
Practice problems
- Activity Selection / Non-overlapping Intervals (sort by end time, worked above)
- Jump Game (greedy reachability, worked above)
- Jump Game II (minimum number of jumps — same reachability idea, plus a window-boundary counter)
- Gas Station (greedy: if total gas >= total cost a solution exists; track running tank deficit to find the start index)
- Fractional Knapsack (greedy by value/weight ratio — contrast directly with 0/1 Knapsack under Dynamic Programming)
- Task Scheduler (greedy + counting, arrange the most frequent task first to minimize idle slots)
- Merge Intervals (sort by start time — a different greedy sort key because the goal is merging, not counting non-overlaps)
Interview angles
- “Prove your greedy choice is optimal” — expect this every time greedy is proposed; the standard proof technique is an exchange argument: take any optimal solution that differs from the greedy choice, show swapping in the greedy choice doesn’t make it worse, therefore some optimal solution contains the greedy choice.
- “Why does this look like DP but is actually greedy (or vice versa)?” — name the greedy-choice property explicitly and give the fractional-vs-0/1-knapsack contrast as the canonical example of where it holds and where it breaks.
- “Why sort by end time and not start time or interval length for scheduling?” — earliest end time leaves maximum room for everything after; a counterexample with start-time sort (a short interval starting early but ending late blocking many short ones) makes the failure concrete.
- “What if intervals have weights (values), not just a count to maximize?” — plain greedy interval scheduling stops working once you’re maximizing total value instead of count; that variant (weighted interval scheduling) needs DP, another good example of the greedy/DP boundary.
- “Can you prove Jump Game’s greedy rule is correct?” — because
farthestis a monotonically non-decreasing running maximum over all reachable indices seen so far, no index that was ever reachable becomes unreachable later, so checkingi <= farthestat each step is sufficient without ever needing to reconsider earlier indices. - “What’s the time complexity if the input isn’t pre-sorted?” — most interval/scheduling greedy solutions are dominated by the O(n log n) sort, not the O(n) scan — be precise that the scan itself is linear and the sort is the bottleneck.