Greedy Algorithms

A greedy algorithm is a problem-solving strategy where you build a solution step by step, and at each step you pick the option that looks best right now (the locally optimal choice). The “hope” is that these locally best choices add up to a globally optimal solution.

Greedy feels natural because it matches how people often make decisions under limited time or information: you commit early, don’t backtrack, and keep moving forward.

Core philosophy of greedy algorithms

Think of hiking up a mountain in heavy fog. You can’t see the peak (the global optimum), but you can see which direction climbs the steepest right at your feet (a local optimum). A greedy strategy says: “Always climb the steepest direction at every step.” The advantage is speed, you gain elevation quickly and you’re always making progress. The danger is that you might end up on a smaller hill (a local maximum) while the true mountain peak is across a valley that requires temporarily going downhill. This is the “greedy trap”: greedy commits too early and refuses moves that look bad locally even if they’re necessary for the best final outcome.

When does greedy work?

For a greedy algorithm to be the “correct” solution, the problem must satisfy two specific mathematical properties:

1. Greedy-choice property: A global optimum can be reached by making a local optimum choice. You don’t need to “look ahead” or reconsider past decisions.
2. Optimal substructure: The optimal solution to the entire problem contains within it the optimal solutions to all its subproblems.

Common “Greedy Problem” patterns

Greedy problems often sound a certain way. You’ll see phrases like “select the maximum number of…” (maximize count under constraints), “minimize total cost/time/resources while satisfying…” (minimize something while meeting constraints), or “always pick the earliest/smallest/largest next…” (suggesting a simple rule plus sorting). Many classic greedy solutions start by sorting the input by a meaningful key—end time, weight, cost, or a ratio—then scanning once while making irreversible decisions.

How to recognize greedy candidates

A quick checklist helps:

• Is there a natural sorting key? (earliest finish time, smallest weight, best ratio)
• Can choices be made irreversibly without regret?
• Does the problem look like scheduling, matching, minimizing resources, or maximizing non-overlap?
• Can you define a “best next move” that does not depend heavily on future arrangement?

If yes, it’s a strong greedy candidate.

The Greedy design process

1. Scan the input: Look for weights, costs, or times.
2. Pick a Rule: Should I pick the smallest? The largest? The best ratio?
3. Test for Failure: Try to find a “counterexample” (like the coin change example).
4. Prove it: Use an Exchange Argument (prove that swapping your choice for another never improves the result).

Key examples

These problems show the most common greedy rules and why they work.

Activity Selection

Problem: You have one room and many meetings (start, end). Pick the maximum number of non-overlapping meetings.

Greedy rule: Sort by end time. Always pick the meeting that finishes earliest.

Why it works: Finishing earlier leaves the most remaining room for other meetings.

Key idea for proof: If an optimal solution picked a meeting that ends later than greedy’s first pick, swapping it with greedy’s earlier-ending meeting can’t reduce the number of meetings you can still schedule.

Complexity: O(n log n) for sorting.

Best Time to Buy and Sell Stock

Problem: Max profit with buy day < sell day.

Greedy rule: Scan once:

• track minimum price so far
• at each price, compute profit if sold today: price - min_so_far
• keep the best profit

Why it works: For every selling day, the best buy day is simply the cheapest earlier price—so you never need to “try all pairs.”

Complexity: O(n) time, O(1) space.

Boats to Save People

Problem: Minimum boats, each boat holds up to 2 people with a weight limit.

Greedy rule: Sort weights. Use two pointers:

• lightest i, heaviest j
• if w[i] + w[j] <= limit: pair them (i++, j–)
• else: heaviest goes alone (j–)

Why it works: The heaviest person is the hardest to fit. If they can’t pair with the lightest, they can’t pair with anyone.

Complexity: O(n log n) sorting, O(n) scan.

Fractional Knapsack

Problem: Max value with weight limit, but you can take fractions of items.

Greedy rule: Sort by value/weight ratio. Take as much as possible from the highest ratio first.

Why it works: Because fractions are allowed, you should always spend your remaining capacity on the “most valuable per kg” item. This is provably optimal.

Complexity: O(n log n) sorting.

The “greedy trap”: when it fails

Greedy is seductive because it’s simple, but it is often wrong.

Problem	Greedy Rule	Result	Why?
0/1 Knapsack	Highest Value/Weight	Fail	Because you can’t take fractions, taking the “best” item might leave a hole in your bag that you can’t fill.
Coin Change	Largest Coin First	Fail	In some systems (e.g., 1, 3, 4), greedy gives 4+1+1 (3 coins) instead of 3+3 (2 coins).
Shortest Path	Closest Node	Fail	If there are negative edges, a path that looks long now might become very “cheap” later.

Greedy vs Dynamic Programming

Feature	Greedy	Dynamic Programming
Decision style	Pick best local choice, commit	Explore combinations via recurrence
Speed/complexity	Usually faster + simpler	Often slower + more complex
Optimality	Not guaranteed without proof	Often guaranteed (when modeled correctly)
Memory	Low	Higher (stores subproblem results)

Complexity and constraints notes

• Most greedy solutions are $O(n log n)$O(nlogn) due to sorting or heaps.
• Some are $O(n)$O(n) if already sorted or using two pointers.
• Memory is usually low ($O(1)$O(1) or $O(n)$O(n)).

Where greedy algorithms are used in real-world applications

Greedy algorithms often appear in problems where you need fast decisions under constraints, without exploring every option. They’re common in optimization tasks involving scheduling, resource allocation, and building efficient solutions step by step.

Greedy is a natural fit for systems that need quick choices, including:

• Scheduling and planning: Selecting the maximum number of compatible tasks/meetings, or picking the next best job by a rule (like earliest finish time).
• Resource allocation: Minimizing resources like boats, rooms, servers, or vehicles by pairing/packing efficiently (often after sorting + two pointers/heaps).
• Network design: Building low-cost connection networks using greedy strategies (e.g., Minimum Spanning Tree for roads, wiring, telecom).
• Data compression: Huffman coding uses greedy merging to create efficient prefix codes.
• Routing (with assumptions): Dijkstra’s algorithm is greedy-based and works when edges are non-negative.
• Fractional selection: When partial choices are allowed (fractional knapsack), greedy maximizes “value per unit.”