Greedy

When to reach for it

• Scheduling: the most non-overlapping meetings, the fewest rooms, the order to run jobs.
• Covering: the fewest stops, refuels or warehouses that cover everything.
• Reachability along a line: how far you can get, or whether you can get to the end.
• The input sorts naturally by one key, and processing it in that order makes each decision obvious.

The core idea

Find the ordering under which one choice is always safe. For picking the most meetings that do not overlap, sort by end time and always take the meeting that ends first: whatever the best schedule picks first, swapping in the earliest-ending meeting cannot make anything else clash. That swap is called an exchange argument, and it is the proof interviewers want to hear.

If you cannot make that argument, test the greedy idea against a small counterexample before you commit. Many questions that look greedy are dynamic programming problems in disguise; coins in unusual denominations are the classic trap.

A Python template

def max_non_overlapping(meetings):
    """The most meetings (start, end) you can attend; touching ends are allowed."""
    count, free_at = 0, float("-inf")
    for start, end in sorted(meetings, key=lambda m: m[1]):   # earliest end first
        if start >= free_at:
            count += 1
            free_at = end
    return count

def loop_start(fuel, cost):
    """Index of a station from which you can drive the whole loop, or -1.
    fuel[i] is picked up at station i; cost[i] is burned driving to i + 1."""
    if sum(fuel) < sum(cost):
        return -1                          # not enough fuel in total
    start, tank = 0, 0
    for i in range(len(fuel)):
        tank += fuel[i] - cost[i]
        if tank < 0:
            start, tank = i + 1, 0         # no station up to i can be the start
    return start

Time and space

Most greedy solutions are a sort plus a pass: O(n log n) time and O(1) or O(n) space depending on whether you sort in place. Some need no sort at all; the loop example is O(n) time and O(1) space.

Common mistakes

• Sorting by the wrong key: by start time or by length instead of by end time for maximum meetings.
• Assuming greedy works without checking a counterexample, then defending a wrong answer.
• Mishandling ties and touching endpoints, which the question usually defines.
• Explaining the code but not why the choice is safe, which leaves the solution looking like a guess.

How to explain it out loud

Say the greedy rule and its justification together: "I take the meeting that ends first, because any schedule that starts differently can swap its first meeting for this one without losing anything." Without the second half, an interviewer cannot tell a proof from a hunch, and the follow-up questions will go after exactly that.

If you considered a greedy rule and rejected it, say so with the counterexample. Then trace your rule on a small input with a tie. Showing you tested the idea before trusting it is what Devana's rubric credits as approach planning and code defense.