Greedy Algorithms Interview Pattern: When to Use It and 5 Problems to Practice (2026)

When you see a coding interview problem that talks about "maximum profit", "minimum cost", "fewest resources", or "earliest deadline", the first instinct should be to ask whether a greedy approach fits. A greedy algorithm makes the best choice it can see right now, without reconsidering earlier decisions. If the problem’s structure guarantees that this local optimum is also a global optimum, the solution is often both simple and fast.

How to Recognize a Greedy Candidate

If you can answer “yes” to any of these, pause and try to formulate a greedy rule.

A Worked Example: Minimum Number of Platforms

Problem (paraphrased). You have a list of train arrival and departure times. Find the minimum number of platforms needed so that no train has to wait.

Why greedy works. The only thing that matters is the order of events. If you process arrivals and departures chronologically, you can keep a running count of how many trains are simultaneously at the station. The maximum count you ever see is the answer. This works because the platform requirement is monotonic – adding a later train cannot reduce the needed count.

Python implementation.

from typing import List, Tuple

def min_platforms(schedule: List[Tuple[int, int]]) -> int:
    """Return the minimum number of platforms required.
    schedule: list of (arrival, departure) times, 24‑hour integer.
    """
    # Flatten into events: +1 for arrival, -1 for departure
    events = []
    for arr, dep in schedule:
        events.append((arr, 1))   # arrival
        events.append((dep, -1))  # departure
    # Sort by time; departures before arrivals at same time
    events.sort(key=lambda x: (x[0], x[1]))

    cur = 0
    best = 0
    for _, delta in events:
        cur += delta
        best = max(best, cur)
    return best

Complexity. Sorting dominates: O(N log N) time, O(N) extra space for the event list.

Common pitfall. Forgetting to order departures before arrivals when times coincide. If a train leaves at 10:00 and another arrives at 10:00, you need only one platform, so the departure should be processed first.

The Greedy Toolkit

1. Sorting‑first strategy – sort items by a key that reflects the greedy rule (deadline, profit/weight ratio, end time, etc.).
2. Single‑pass scan – walk the sorted list, maintaining a simple state (current sum, count, heap of chosen items).
3. Priority queue fallback – when you need to replace a previously chosen element with a better one, a min‑heap lets you drop the worst quickly.
4. Two‑pointer technique – useful for interval‑based problems where you advance a left and right pointer in lockstep.

Five Practice Problems

1. Activity Selection (Maximum Non‑Overlapping Intervals)

Goal: Choose the largest set of compatible activities. Greedy rule: Sort by finishing time, then pick each activity whose start is after the last chosen finish. Hint: After sorting, a single pass yields the answer.

2. Fractional Knapsack (Maximum Value with Unlimited Divisibility)

Goal: Fill a knapsack of capacity C with items of weight w and value v to maximize total value. Greedy rule: Sort by value‑per‑weight ratio, take as much as possible of each item in that order. Hint: The optimal solution may include a fraction of the last item.

3. Minimum Cost to Connect Sticks (Huffman‑style Merging)

Goal: Given stick lengths, repeatedly connect two sticks; cost = sum of lengths. Minimize total cost. Greedy rule: Always merge the two shortest sticks first. Hint: Use a min‑heap to retrieve the smallest lengths efficiently.

4. Job Sequencing with Deadlines (Maximum Profit)

Goal: Schedule jobs each taking one unit of time before its deadline, each with a profit. Greedy rule: Sort jobs by profit descending, then place each job in the latest free slot before its deadline. Hint: A disjoint‑set union (DSU) structure can find the latest available slot quickly.

5. Allocate Minimum Number of Cookies (Fair Distribution)

Goal: Given children’s greed factors and cookie sizes, maximize satisfied children. Greedy rule: Sort both lists, then give each child the smallest cookie that meets its greed. Hint: Walk both arrays with two pointers.

When Greedy Fails

• Non‑matroid constraints: If picking an element can invalidate a later, better choice, greedy may get stuck.
• Global dependencies: Problems where the optimal solution depends on a combination of items (e.g., classic 0/1 knapsack) usually need DP.
• Counter‑example traps: Always test your rule on a small adversarial case. If you can construct a scenario where a locally optimal step leads to a worse overall outcome, the greedy approach is unsafe.

How to Practice This

1. Identify the greedy key – for each new problem, write down the ordering criterion (deadline, ratio, end time) before coding.
2. Implement a skeleton – start with sorting and a single pass; add a heap only if you need to replace a previous choice.
3. Rehearse your explanation – use Call Assistant to practice a 45‑second walkthrough, focusing on why the greedy rule is correct and what the main pitfall is.

FAQ

• Q: How can I tell if a problem is a matroid? A: Look for an “exchange property”: if you have two feasible sets and one is larger, you can swap an element from the larger set with one from the smaller while staying feasible. When this holds, greedy is provably optimal.

• Q: Why does sorting by profit/weight ratio work for fractional knapsack but not 0/1 knapsack? A: Fractional knapsack allows breaking items, so the ratio directly determines marginal benefit. In 0/1 knapsack you must take whole items, creating combinatorial constraints that break the ratio rule.

• Q: Should I always use a heap for greedy problems? A: No. If the greedy rule only needs the next smallest or largest element once per iteration, a simple sort plus index works. Use a heap when you need repeated extraction of the current optimum.

• Q: How much time should I spend on each practice problem? A: Aim for a 30‑minute cycle: 5 minutes to read and outline the greedy rule, 15 minutes to code, 5 minutes to test edge cases, and 5 minutes to verbally explain the solution.