Recap — When Greedy Works (and When It Doesn't)

# When Greedy Works (and When It Doesn't) Greedy: make the locally optimal choice at each step, hope it leads to global optimum. When it works, it's fast (O(N log N) typically). When it doesn't, your answer is just wrong. ## Greedy works when... The problem has the "greedy choice property": a locally optimal choice leads to a globally optimal solution. ### Example: Interval scheduling "Given N intervals, pick the maximum number that don't overlap." Greedy: sort by END time. Pick first; then pick the next one whose start ≥ previous end. ```python def max_intervals(intervals): intervals.sort(key=lambda x: x[1]) # sort by end count = 0 last_end = float('-inf') for start, end in intervals: if start >= last_end: count += 1 last_end = end return count ``` Why end-time? Picking the earliest-ending interval leaves maximum room for future ones. Proof: exchange argument — any optimal solution can be converted to use earliest-ending without losing intervals. ### Example: Merge intervals "Merge overlapping intervals." ```python def merge(intervals): intervals.sort(key=lambda x: x[0]) # sort by start result = [] for start, end in intervals: if result and result[-1][1] >= start: result[-1][1] = max(result[-1][1], end) else: result.append([start, end]) return result ``` Sort by start, sweep, merge. ### Example: Activity selection Same as interval scheduling. Sort by end, pick greedily. ## Greedy doesn't work for... ### Coin change (general denominations) "Min coins to make amount." If coins are [1, 5, 10, 25] (US currency), greedy works: always pick the largest coin ≤ remaining amount. But for coins [1, 3, 4] and amount 6: - Greedy: 4 + 1 + 1 = 3 coins. - Optimal: 3 + 3 = 2 coins. Greedy fails. Need DP. The lesson: **greedy works only when the problem structure guarantees it**. For arbitrary denominations, it doesn't. ### Knapsack (0/1) Greedy by value-per-weight (fractional knapsack) works for fractional knapsack. For 0/1 knapsack (take whole item or not), it fails. Need DP. ## How to spot a greedy problem Signals: - "Maximum number of X you can do." - "Schedule activities." - "Fewest groups / rooms / changes." - Sortable by some natural ordering. Counter-signals: - "Optimal AND counting all ways." → DP for counting. - "0/1 take-or-leave knapsack" → DP. - Constraints don't have a clean local choice → DP. ## Proving greedy correctness Two common arguments: 1. **Exchange argument**: assume an optimal solution differs from greedy at some step. Show you can swap that choice to match greedy without losing optimality. 2. **Greedy stays ahead**: show that after each step, greedy's choice is at least as good as any other strategy's. In interviews, you don't need formal proofs but should articulate the intuition: "I'm picking earliest-ending because that leaves the most room for future intervals." ## Greedy patterns ### Sort first Most greedy problems start with sorting by a relevant key: - Intervals: by start or end - Tasks: by deadline or duration - Items: by ratio (value/weight) ### Priority queue + greedy For online/streaming problems, use a heap: ```python def k_largest_sum(arr, k): h = [] for x in arr: heapq.heappush(h, x) if len(h) > k: heapq.heappop(h) return sum(h) ``` The heap maintains the K most relevant items. ### Two-pass Sometimes greedy works only after multiple passes: ```python def candy(ratings): n = len(ratings) candy = [1] * n # Left to right pass for i in range(1, n): if ratings[i] > ratings[i-1]: candy[i] = candy[i-1] + 1 # Right to left pass for i in range(n-2, -1, -1): if ratings[i] > ratings[i+1]: candy[i] = max(candy[i], candy[i+1] + 1) return sum(candy) ``` Each pass enforces a local constraint; together they give the global answer. ## Common greedy mistakes 1. **Assuming greedy works without checking.** "Largest first" or "earliest first" doesn't always work; test with counter-examples. 2. **Wrong sort key.** "Sort by start" vs "sort by end" matter; one might fail. 3. **Greedy when DP is needed.** If you can construct a counter-example, switch to DP. 4. **Not considering ties.** When two intervals end at same time, does it matter which you pick? Sometimes yes (use second key). ## Takeaway Greedy = local optimal → global optimal, when problem allows it. Recognize by: maximize/minimize count, schedule activities, fewest changes. Start by sorting on the right key. Test with counter-examples before committing. When greedy fails, DP usually works. Classic problems: interval scheduling (sort by end), merge intervals (sort by start), candy distribution (two-pass), Dijkstra (heap-greedy).