Greedy

What is greedy?

A greedy algorithm makes the choice that looks best right now, without reconsidering past choices or looking ahead. At each step it picks the locally optimal option and moves on. This works when the greedy choice property holds: a locally optimal choice is always part of a globally optimal solution. When that property holds, greedy produces the global optimum in a single pass.

The key contrast with dynamic programming: DP considers all choices and caches overlapping subproblems. Greedy commits to one choice at each step. If the problem has the greedy choice property, greedy is faster - usually O(n log n) for the initial sort plus O(n) for the scan, versus O(n^2) or O(nk) for DP.

The exchange argument is the standard proof technique for greedy correctness. Assume an optimal solution differs from the greedy solution at some step. Show you can swap the optimal choice for the greedy choice without making the solution worse. If that swap is always safe, the greedy choice is always correct - the optimal solution can be transformed step by step into the greedy solution without losing quality.

Interval scheduling is the canonical greedy domain. Given a set of intervals, select the maximum number of non-overlapping ones. The greedy rule: always pick the interval that ends earliest. Intuitively, the earliest-ending interval leaves the most remaining time for future intervals. The exchange argument confirms it: if an optimal solution skips the earliest-ending interval in favor of a longer one, you can swap in the shorter one without reducing the count.

Core operations

Key patterns

Interval scheduling

Walk the intervals in order of when they finish and grab each one that does not collide with the last one you took.

When to use - you are handed a set of intervals and asked for the most you can pick without any two overlapping: maximum non-overlapping meetings, fewest intervals to remove, most activities you can attend. A brute-force search over every subset is exponential. Greedy works here only because picking the earliest-finishing interval is provably safe - the exchange argument shows swapping it in never lowers the count - so be honest that the trick fails the moment a local pick is not provably globally optimal.

How it works - sort by end time, not start time, then scan once. Keep last_end and accept an interval when its start is at or after last_end, updating last_end to the accepted interval's end. The end-time sort is the whole game: after each accept, the last interval you took finishes as early as possible, which leaves the widest remaining window for everything still ahead. The exchange argument proves it - if an optimal solution skipped the earliest-finishing interval, you could swap that interval in without reducing the count. The sort costs O(n log n) and dominates the O(n) scan.

Greedy with a running extreme (jump game)

Sweep left to right while carrying one number: the farthest index you could reach from anything you have seen so far.

When to use - the question is "can you reach the end?" or "what is the fewest moves to get there?" and the whole state collapses to a single running maximum. Reach for it when no earlier choice locks you out of a later one, so a left-to-right sweep with one local rule suffices and full dynamic programming is overkill. As always with greedy, this only holds because the local choice - always extend the frontier as far as possible - is provably the global optimum here.

How it works - keep farthest, the best index reachable so far. At each index, first check reachability: if index > farthest, you have hit a gap and can stop. Only then update farthest = max(farthest, index + nums[index]). The order matters - extending the frontier from a position you cannot actually reach would paper over the gap. For minimum jumps, treat each jump's reach as a level boundary: when the scan crosses the current boundary, take one jump and advance the boundary to farthest. This is valid because every index inside a level is equally one jump away, so the only question is how far the level stretches. One pass, O(n).

Canonical examples

Meeting rooms II (minimum rooms needed)

Count the maximum number of overlapping intervals at any point - that equals the minimum number of rooms required. Sort meetings by start time, then maintain a min-heap of end times of in-progress meetings. For each new meeting, if the earliest-ending ongoing meeting has already ended, reuse that room. Otherwise open a new one.

Jump game II (minimum jumps)

Greedy: track the farthest position reachable within the current "level" (all positions reachable in exactly the same number of jumps). When the scan steps past the current level's boundary, increment the jump count and advance the boundary to the farthest position found so far. Every position within a level is equally one jump away, so the only question is how far the level can extend.

When to reach for greedy

• The problem involves selecting a subset of intervals to maximize count or minimize overlap.
• You need the minimum number of resources (rooms, platforms, workers) to handle a set of concurrent tasks.
• The problem has a clear ordering (by end time, deadline, ratio) after which the best local choice is obvious at each step.
• An exchange argument convinces you: swapping any greedy choice for a different choice cannot improve the result.
• DP feels like overkill - the problem has no recombining subproblems, just a single left-to-right sweep.
• The problem asks for the minimum number of operations, jumps, or arrows to cover or reach all targets.
• The question is "can you reach the end?" or "what is the fewest moves?" and the state reduces to a single running maximum.

Practice problems

• Jump Game - Greedy reachability frontier; boolean answer.
• Jump Game II - Level-by-level greedy; minimum jumps.
• Meeting Rooms II - Min rooms equals max concurrent meetings.
• Merge Intervals - Sort by start, merge overlapping pairs.
• Non-overlapping Intervals - Maximum non-overlapping equals total minus minimum removals; sort by end time.
• Gas Station - Greedy: if total gas ≥ total cost a solution exists; start where the running sum bottoms out.