Greedy algorithms make the locally optimal choice at each step, hoping to find the global optimum. Unlike dynamic programming which explores all possibilities, greedy commits to each decision and never backtracks. The challenge is proving that the greedy choice leads to an optimal solution. This guide covers the greedy patterns most commonly tested in coding interviews with proofs of correctness and implementation details.
When Does Greedy Work?
Greedy works when the problem has two properties: (1) Greedy choice property — a globally optimal solution can be arrived at by making a locally optimal choice. You never need to reconsider a choice once made. (2) Optimal substructure — an optimal solution to the problem contains optimal solutions to subproblems (shared with dynamic programming). If the greedy choice property does not hold, greedy fails. Example: coin change with denominations [1, 3, 4] and target 6. Greedy picks 4+1+1=3 coins. Optimal is 3+3=2 coins. Greedy fails because picking the largest coin first does not lead to the optimal solution. How to verify greedy works: (1) Sort by a criterion. (2) Process items in order, making the greedy choice. (3) Prove (by exchange argument or contradiction) that any other choice cannot improve the result. In interviews, you often do not need a formal proof — explaining the intuition for why greedy is correct is sufficient.
Pattern 1: Interval Scheduling
Maximum non-overlapping intervals: given a set of intervals, find the maximum number of non-overlapping intervals. Greedy strategy: sort by end time. For each interval: if it does not overlap with the last selected interval, select it. Why end-time sorting: selecting the interval that finishes earliest leaves the most room for subsequent intervals. Proof by exchange: if an optimal solution selects an interval that ends later than our greedy choice, we can swap it for our earlier-ending choice without reducing the count (the earlier end creates more room). Time: O(N log N) for sorting. Minimum intervals to remove for non-overlapping: equivalent to N – maximum_non_overlapping. Merge overlapping intervals: sort by start time. Iterate: if the current interval overlaps with the previous (current.start <= prev.end), merge by extending prev.end = max(prev.end, current.end). Else start a new merged interval. Meeting rooms II (minimum rooms needed): sort events by time. Use a min-heap of end times. For each meeting: if it starts after the earliest ending meeting, reuse that room (pop from heap). Add the new meeting end time to the heap. The heap size is the answer.
Pattern 2: Jump Game and Reachability
Jump Game I: given an array where each element is the maximum jump length, determine if you can reach the last index. Greedy: maintain the farthest reachable index. Iterate from left to right: if the current index is beyond the farthest reachable, return false. Update farthest = max(farthest, i + nums[i]). If farthest >= last index, return true. Time: O(N). Jump Game II: find the minimum number of jumps. Greedy (BFS-like): maintain the current jump end boundary and the farthest reachable. When you reach the current boundary, you must jump (increment jump count) and set the new boundary to farthest. Time: O(N). Gas Station: circular route with gas stations. Greedy: if total gas >= total cost, a solution exists. Find the starting station: iterate, maintaining a running surplus. When surplus drops below 0, the start must be the next station (all previous stations are invalid starts). Time: O(N). These problems share the pattern: scan left to right, maintain a “best so far” variable, and make decisions based on accumulated information.
Pattern 3: Task Scheduling and Arrangement
Task Scheduler: given tasks with a cooldown period N between same tasks, find the minimum time to complete all tasks. Greedy: the most frequent task determines the minimum time. Calculate: (max_freq – 1) * (N + 1) + count_of_tasks_with_max_freq. If the total tasks exceed this formula result, the answer is the total task count (no idle time needed). Reorganize String: rearrange a string so no two adjacent characters are the same. Greedy with a max-heap: always place the most frequent remaining character. After placing, push the previously placed character back (it can be used again after one position gap). If the most frequent character count > ceil(N/2), it is impossible. Assign Cookies: give cookies to children greedily. Sort both children (by greed factor) and cookies (by size). Assign the smallest sufficient cookie to the least greedy child. This maximizes the number of satisfied children. These problems share: identify the bottleneck (most constrained element), handle it first, and let remaining elements fill in.
Pattern 4: Greedy with Sorting
Many greedy problems require sorting by a specific criterion. The key is choosing the right sort order. Minimum number of arrows to burst balloons: sort by end point. Shoot at the end of the first balloon. All overlapping balloons at that point burst. Move to the next unbursted balloon. Identical to the interval scheduling pattern. Non-overlapping intervals minimum removal: same as maximum non-overlapping intervals. Queue reconstruction by height: people described by (height, count of taller people in front). Sort by height descending, then by count ascending. Insert each person at position = their count. The tall people are placed first; shorter people inserted later do not disrupt taller placements. Boats to save people: sort by weight. Two pointers (lightest and heaviest). If they fit in one boat together, pair them. Otherwise, the heaviest goes alone. Minimum changes to make alternating binary string: count mismatches for both “0101…” and “1010…” patterns. The answer is the minimum count. Greedy + sorting tip: if the problem involves optimal pairing, ordering, or selection, try sorting by the most constraining attribute first. The sort criterion is the key insight — once you find it, the algorithm is straightforward.
Greedy vs Dynamic Programming
How to decide: (1) If the problem has obvious greedy structure (intervals, scheduling, always-forward progress), try greedy first. Greedy solutions are simpler and faster. (2) If greedy produces a wrong answer on a simple example, switch to DP. The coin change example: greedy picks largest coin first but misses the optimal combination. DP explores all combinations. (3) Some problems can be solved by either. Jump Game II is solvable by greedy (O(N)) and DP (O(N^2)). The greedy solution is preferred. (4) If the problem asks for “all possible solutions” or “count the number of ways,” greedy usually does not apply (it finds one solution, not all). Use DP or backtracking. Practice problems: (1) Interval scheduling — merge intervals, non-overlapping intervals, meeting rooms. (2) Jump/reachability — Jump Game I and II, Gas Station. (3) Task arrangement — Task Scheduler, Reorganize String. (4) Greedy + sort — Assign Cookies, Queue Reconstruction, Boats to Save People. Solve 3-5 per pattern. The sort criterion and greedy insight are the skills to develop.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”When does a greedy algorithm produce an optimal solution?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Greedy works when the problem has two properties: (1) Greedy choice property — making the locally optimal choice at each step leads to a globally optimal solution. You never need to reconsider. (2) Optimal substructure — the optimal solution contains optimal subsolutions. If greedy choice property does not hold, greedy fails. Classic failure: coin change with denominations [1,3,4], target 6. Greedy picks 4+1+1=3 coins. Optimal is 3+3=2 coins. How to verify: sort by a criterion, process items greedily, and argue (exchange argument) that any other choice cannot improve the result. In interviews, intuitive explanation suffices — formal proofs are rarely required. If you can construct a counterexample where greedy fails, switch to dynamic programming.”}},{“@type”:”Question”,”name”:”How do you solve interval scheduling problems with greedy?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Maximum non-overlapping intervals: sort by end time. Select the first interval. For each subsequent interval: if it starts after the last selected interval ends, select it. This maximizes the count because selecting the earliest-ending interval leaves maximum room for future selections. Time: O(N log N) for sort. Minimum intervals to remove: answer = N – max_non_overlapping. Merge overlapping intervals: sort by start time. If current overlaps previous (current.start farthest, unreachable — return false. Update farthest = max(farthest, i + nums[i]). If farthest >= last index, return true. Time: O(N). Jump Game II (minimum jumps): BFS-like greedy. Track current_end (boundary of current jump) and farthest (farthest reachable). When you reach current_end, you must jump: increment jumps, set current_end = farthest. Time: O(N). Gas Station: if total gas >= total cost, solution exists. Find starting station by iterating with running surplus. When surplus drops below 0, start must be the next station. Time: O(N). These share the pattern: scan left to right, maintain a running best so far metric, make irreversible decisions based on accumulated information. The forward-only scan is the hallmark of greedy reachability problems.”}},{“@type”:”Question”,”name”:”How do you decide between greedy and dynamic programming?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Decision guide: (1) Try greedy first if the problem has obvious structure: intervals, scheduling, always-forward progress, or pairing/matching. Greedy is simpler and faster. (2) Test with a small counterexample. If greedy gives wrong answer (coin change with [1,3,4], target 6), switch to DP. (3) If the problem asks for all solutions or count the number of ways, greedy usually does not apply. Use DP or backtracking. (4) Some problems can be solved by both: Jump Game II is O(N) greedy or O(N^2) DP. Prefer greedy. (5) Optimization problems with overlapping subproblems almost always need DP. Greedy makes one pass; DP explores all possibilities. Key difference: greedy makes irrevocable choices, DP considers all options. If making the locally best choice always leads to globally best, use greedy. If you need to compare multiple paths, use DP.”}}]}