Introduction to Greedy Algorithm

A greedy algorithm builds a solution incrementally by, at every step, committing to the single choice that looks best right now under some selection rule — and never revisiting that commitment — which only yields a globally optimal answer when the problem provably has two properties: the greedy-choice property (some locally best pick is always part of a globally best solution) and optimal substructure (an optimal solution to the whole problem is built from an optimal solution to the remaining subproblem after that pick).

Recognize the pattern

• The task asks for a min/max count, min/max cost, or a feasibility packing under one simple constraint (interval scheduling, canonical-coin change, boat/room/task pairing, minimum spanning tree, Huffman coding).
• Sorting the input by some key (weight, finish time, ratio) makes an exchange argument work: swapping any two adjacent choices in an optimal solution never makes it worse, so the sorted order can be followed greedily.
• Decisions are irrevocable — nothing is ever undone or re-tried, unlike DP where subproblems are re-evaluated and combined.
• You cannot construct a counterexample where the locally-best pick provably harms the global result — if you can, it is not a greedy problem (try DP instead).

Brute force → optimal: Boats to Save People

Problem: array people[i] is the weight of person i; each boat carries at most 2 people with combined weight ≤ limit; find the minimum number of boats for everyone.

Brute force: try every way of partitioning the n people into groups of size 1 or 2 respecting the limit, and keep the partition with fewest groups. The number of such partitions grows super-exponentially (double-factorial-like), so this is effectively O(2^n) or worse time, infeasible past n≈20–25, plus O(n) space per partition attempt.

Greedy optimal: sort ascending, then use two pointers — i at the lightest person, j at the heaviest. If people[i] + people[j] ≤ limit, pair them (advance both pointers); otherwise the heaviest person must ride alone (advance only j). Repeat until the pointers cross. Why greedy is safe: the heaviest remaining person always needs a boat, and if anyone can share it, the lightest remaining person is the one least likely to force a wasted seat elsewhere — pairing them first never costs an extra boat versus any other pairing choice (exchange argument: swapping the lightest partner for any other feasible partner of the heaviest person can only reduce or keep equal the remaining capacity used). To complete the proof, check both swapped boats stay feasible: suppose an optimal solution pairs heaviest h with some x and lightest l with some y; swap partners to get (h,l) and (x,y). Then h + l ≤ h + x ≤ limit because l is the lightest (l ≤ x), and x + y ≤ x + h ≤ limit because h is the heaviest (y ≤ h) — both boats remain legal and the boat count is unchanged, so the greedy pairing is never worse than any optimal one.

Complexity, derived

Time: sorting is O(n log n) comparisons (standard comparison-sort lower bound). The two-pointer sweep does at most n pointer advances total (each iteration advances j always, and sometimes i too, and the loop ends when i > j), so the sweep is O(n). Total: O(n log n), dominated by the sort.

Space: sorting in place (e.g. Arrays.sort on primitives) uses O(log n) stack space for its internal quicksort/dual-pivot recursion; the two pointers and boat counter are O(1). Total: O(log n) auxiliary space (or O(1) if you count only your own variables).

Compare the brute-force partition search: enumerating all pairings is O(2^n) to O(n!) time depending on formulation, with recursion depth (space) up to O(n).

Traced worked example

people = [10, 55, 70, 20, 90, 85], limit = 100. Sorted: [10, 20, 55, 70, 85, 90], indices 0..5.

Result: 4 boats, matching the expected output.

Reference implementation (Java)

import java.util.Arrays;

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int i = 0, j = people.length - 1;
        int boats = 0;
        while (i <= j) {
            if (people[i] + people[j] <= limit) {
                i++; // lightest person pairs with heaviest
            }
            j--; // heaviest person always leaves in this boat
            boats++;
        }
        return boats;
    }
}

Pitfalls

• Assuming greedy always works. For 0/1 knapsack, greedily taking the highest value/weight ratio item can be strictly worse than the optimal DP solution — there is no exchange argument that holds because items cannot be split or partially reversed.
• Skipping the proof. A greedy rule that works on the sample input can still fail on an adversarial one; without an exchange-argument or matroid justification, it is a heuristic, not a correct algorithm.
• Forgetting irrevocability's cost. Once a choice is locked in, greedy cannot backtrack, so a subtly wrong selection function (e.g., sorting by start time instead of finish time for interval scheduling) silently produces a suboptimal answer with no error signal.
• Off-by-one in pointer sweeps. Using i < j instead of i <= j undercounts the boat for the last unpaired middle person.

When to use / when not — vs. Dynamic Programming

Use greedy when you can prove the greedy-choice property and optimal substructure hold (interval scheduling, MST via Kruskal/Prim, Huffman coding, fractional knapsack, this boats problem). It gives the best achievable complexity, usually a sort plus a linear scan, with O(1)–O(log n) extra space.

Use dynamic programming instead when locally best choices can lock you out of the global optimum — e.g., 0/1 knapsack, longest common subsequence, coin change with arbitrary (non-canonical) denominations. Concrete counterexample: coins {1, 3, 4}, amount 6 — greedy takes 4+1+1 = 3 coins, but the optimum is 3+3 = 2 coins; coin greedy is only safe for canonical systems (like standard currency denominations), and arbitrary denominations need DP. DP explores overlapping subproblems and combines them via a recurrence, trading higher time/space (often O(n·W) or O(n²)) for guaranteed correctness where greedy cannot be proven.

Trade-off summary: greedy is faster and simpler but requires a correctness proof unique to each problem; DP is more broadly applicable and always correct for optimal-substructure problems but costs more time and space.

Takeaways

• Greedy is correct only when greedy-choice property + optimal substructure both hold — always look for the exchange argument before trusting it.
• The pattern is almost always: sort by the right key, then make one irrevocable linear pass.
• Complexity is typically dominated by the sort, O(n log n) time, with the greedy pass itself O(n) time and O(1) extra space.
• When greedy's proof fails or a counterexample exists, fall back to dynamic programming.

Recall question: Why does pairing the lightest remaining person with the heaviest remaining person (rather than any other pairing) never increase the total number of boats needed?

Adapted and expanded from the source notes on Greedy Algorithms, with added complexity derivation, worked trace, exchange-argument justification, and DP comparison for interview-level depth.