Greedy Algorithms

Greedy commits to one next choice instead of exploring alternatives. The key interview work is to justify why that choice cannot prevent an optimal completion. A rule that passes a few examples is still only a candidate.

1. Test the Choice Before Coding

State the objective, the exact choice rule, and what becomes unavailable after choosing. Then try small inputs where an attractive choice blocks two better choices later.

• Fewest coins: with denominations [1, 3, 4] and target 6, taking the largest coin first yields 4+1+1; the optimum is 3+3. General coin change needs Dynamic Programming.
• Most non-overlapping intervals: choosing the earliest start fails for closed intervals [0,10], [1,2], [3,4]. The first interval blocks two compatible intervals.
• 0/1 knapsack: highest value/price ratio fails with budget 10 and (price,value) items (4,5), (5,6), (5,6). The ratio-first choice leads to value 11; the two price-5 items give 12. Items cannot be split.

Failing to find a counterexample is useful, but is not a proof. Two common arguments are an exchange that replaces an optimal solution's first differing choice with yours without worsening it, or a stays-ahead invariant showing your partial result leaves at least as much future opportunity.

2. Select the Most Non-overlapping Intervals

For closed intervals [start,end] with start < end, maximize the number selected. Sort by end time and accept an interval only if it begins strictly after the previous accepted end.

def most_non_overlapping(intervals):
    last_end = float('-inf')
    count = 0
    for start, end in sorted(intervals, key=lambda item: item[1]):
        if start > last_end:
            count += 1
            last_end = end
    return count

Why earliest finish works: let g be the earliest-finishing available interval, and let an optimum start with o. Replacing o with g preserves the count and cannot block a later interval because g ends no later. Repeat this argument on the remaining intervals. The selected intervals remain compatible, and their final endpoint leaves as much room as possible for the next choice.

For half-open intervals [start,end), touching endpoints are compatible, so use start >= last_end. Sorting costs $O(n\log n)$ time and $O(n)$ space for this Python implementation; the scan uses $O(1)$ additional state. Maximizing total interval weight is a different problem: earliest finish no longer suffices.

3. Reachability, Minimum Jumps, and Restarting

These applications use different invariants; do not memorize one vague “pick the best” rule.

For Gas Station, if candidate s first fails at i, every prefix before i has nonnegative balance. Starting later at t removes such a prefix from the negative total through i, so it cannot fix the failure. Restart at i+1. A negative total balance makes a full circuit impossible; a nonnegative total permits the surviving candidate. This assumes an unlimited tank and the standard circular route.

All three scans take $O(n)$ time and $O(1)$ space. Jump Game uses nonnegative jump lengths. For a minimum-jump problem that does not guarantee reachability, detect a boundary that cannot advance and report failure; a one-element array needs zero jumps.

4. Key Takeaways

• Before implementing a greedy rule, try one attractive choice that blocks two compatible choices.
• For the maximum count of intervals, choose earliest finish; write down whether touching endpoints overlap.
• Minimum jumps processes an entire reachable layer before increasing the jump count; choosing only the locally longest jump is not the same algorithm.
• In Gas Station, justify skipping the whole failed segment and separately check the total balance.

Sorting often establishes greedy processing order; Heaps maintain that order when candidates arrive dynamically. If no safe choice can be justified, model the alternatives with Backtracking, then look for overlapping states in Dynamic Programming.