Greedy Algorithms

A greedy algorithm builds the answer one step at a time and always takes the choice that looks best right now, never reconsidering it. When it works it is usually the simplest and fastest solution, but it only works for problems where a local choice can be proven safe. In an interview, the code is short; the real work is choosing the right greedy rule and convincing the interviewer it is correct.

Intuition

Greedy works when the problem has two properties:

• Greedy choice property: some optimal solution starts with the choice the greedy rule makes.
• Optimal substructure: after making that choice, what remains is a smaller instance of the same problem.

Two standard ways to argue the first property:

1. Exchange argument. Take any optimal solution that differs from the greedy one. Swap an element (often two adjacent elements) to agree with the greedy choice and show the result is still feasible and no worse. Repeating the swap turns any optimal solution into the greedy one.
2. Greedy stays ahead. Show by induction that after every step the greedy partial solution is at least as good as any other partial solution of the same size.

Before proving anything, try to break your rule. Small counterexamples kill wrong greedy ideas quickly. For coins [1, 3, 4] and amount 6, "take the largest coin first" uses 4 + 1 + 1 (three coins), while 3 + 3 uses two. That problem needs dynamic programming.

When to use it in interviews / OAs

• Intervals and scheduling: choose the most non-overlapping meetings, the fewest arrows to burst balloons, the fewest rooms.
• "Minimum number of X to cover / reach Y": jump game, refueling stops, covering a range with taps.
• Pairing after sorting: assign cookies to children, boats carrying two people, matching the largest with the smallest.
• Repeatedly take the best available item: merging ropes or files at minimum cost, reorganizing a string, maximizing capital across projects. A heap provides the best item in O(log n).
• Ordering problems: arrange items to minimize total waiting time or to form the largest number. The sort key comes from an exchange argument.
• Constraints around 10^5 with no obvious DP state small enough usually point to an O(n log n) greedy.

Template

Most interview greedy solutions are one of three shapes.

1. Sort, then scan

Pick the maximum number of non-overlapping half-open intervals [start, end). Choosing the interval that finishes first leaves the most room for the rest; an exchange argument shows that replacing the first interval of any optimal answer with the earliest-finishing one never causes a conflict.

def max_non_overlapping(intervals: list[tuple[int, int]]) -> int:
    count, last_end = 0, float("-inf")
    for start, end in sorted(intervals, key=lambda iv: iv[1]):  # earliest finish first
        if start >= last_end:  # touching intervals do not overlap
            count += 1
            last_end = end
    return count

2. Derive the sort key with an exchange argument

One machine must run jobs with durations t and weights w; minimize the sum of w * finish_time. Look at two adjacent jobs a and b. Everything before and after them is unaffected by their order, and putting a first costs w_a * t_a + w_b * (t_a + t_b) versus w_b * t_b + w_a * (t_a + t_b) the other way. So a should go first exactly when t_a * w_b < t_b * w_a, that is, by increasing t / w. Compare with cross-multiplication to stay in exact integer arithmetic:

from functools import cmp_to_key


def min_weighted_completion(jobs: list[tuple[int, int]]) -> int:
    """jobs = [(duration, weight)] with duration >= 1. Minimize sum(weight * finish time)."""
    def order(a: tuple[int, int], b: tuple[int, int]) -> int:
        return a[0] * b[1] - b[0] * a[1]  # negative means a goes first

    total = time = 0
    for duration, weight in sorted(jobs, key=cmp_to_key(order)):
        time += duration
        total += weight * time
    return total

The same adjacent-swap technique produces many classic orderings: all weights equal gives "shortest job first", and concatenating numbers into the largest number compares x + y against y + x as strings.

3. Heap-based and regret greedy

Each job takes one unit of time, must finish by its deadline and pays a profit; maximize total profit. Process jobs by deadline and tentatively accept every job. If the accepted jobs no longer fit before the current deadline, drop the least profitable one accepted so far. A min-heap makes "find the worst choice" cheap:

import heapq


def max_profit_with_deadlines(jobs: list[tuple[int, int]]) -> int:
    """jobs = [(deadline, profit)]; each job takes one unit of time."""
    kept: list[int] = []  # min-heap of profits of the jobs we currently plan to do
    for deadline, profit in sorted(jobs):
        heapq.heappush(kept, profit)  # take it for now
        if len(kept) > deadline:      # cannot fit them all before this deadline
            heapq.heappop(kept)       # regret: give up the least profitable job
    return sum(kept)

When the cheapest two items should always be combined first, the heap alone is the algorithm. Merging sticks where each merge costs the sum of the two lengths is Huffman coding in disguise:

def min_merge_cost(sticks: list[int]) -> int:
    heap = list(sticks)
    heapq.heapify(heap)
    cost = 0
    while len(heap) > 1:
        a, b = heapq.heappop(heap), heapq.heappop(heap)  # two cheapest
        cost += a + b
        heapq.heappush(heap, a + b)
    return cost

Complexity

• Sort-then-scan: O(n log n) for the sort, O(n) for the scan, O(n) space for the sorted copy (O(1) extra if you sort in place).
• Heap-based greedy: O(n log n) time and O(n) space.
• Most greedy solutions are dominated by the sort; this is why greedy beats DP when n is large.

Common pitfalls

• No proof, wrong rule. Sorting intervals by start time or by length does not maximize the number of non-overlapping intervals; sorting by end time does. Test the rule on tiny inputs against brute force.
• Greedy where DP is required. 0/1 knapsack and coin change with arbitrary coins are not greedy; fractional knapsack is.
• Floating-point ratios in sort keys. Compare a.t * b.w with b.t * a.w instead of dividing; it is exact and handles zero weights.
• Inconsistent comparators. A custom comparator must define a consistent order (if a before b and b before c, then a before c), otherwise sorting can produce garbage.
• Boundary semantics. Decide whether intervals that touch at an endpoint overlap, and use >= or > accordingly.
• Forgetting the regret option. If a plain greedy fails because an early choice blocks a better later one, consider "accept now, drop the worst later" with a heap.

Interview variations

• Interval family: non-overlapping intervals (remove the fewest), minimum arrows, meeting rooms (heap of end times), merge intervals.
• Reachability: jump game (track the farthest reachable index), jump game II (BFS by layers), gas station (reset the start when the tank goes negative).
• Two-sided passes: candy distribution (left-to-right, then right-to-left), trapping-water-style constraints.
• Sorting plus two pointers: boats to save people, assign cookies.
• Heap greedy: task scheduler, reorganize string, IPO (one heap for affordable projects, one for locked ones), course schedule with deadlines (the regret pattern above).
• Custom orderings: largest number, queue reconstruction by height (sort tall first, insert by index), weighted job ordering.