Greedy Algorithms and Their Applications

From DP to greedy

In Dynamic Programming Essentials, you solved optimization problems by keeping track of many smaller answers. Greedy algorithms ask a sharper question:

Can I make the best-looking choice right now and never regret it?

That sounds risky, and it is. But when the problem has the right structure, greedy solutions are often simpler, faster, and easier to implement than DP.

Today’s goal

By the end of this lesson, you should be able to:

• Recognize common greedy patterns
• Sort choices in a useful order
• Explain why a local choice is safe
• Know when greedy is probably not safe
• Solve beginner-to-medium problems like interval scheduling and Jump Game

This fits the 30-day crash course well: greedy problems appear often in interviews because they test both coding and reasoning.

The greedy mindset

A greedy algorithm builds a solution one decision at a time. At each step, it chooses the option that looks best according to some rule.

Common greedy rules include:

• Pick the smallest cost
• Pick the earliest finishing item
• Pick the largest benefit
• Pick the choice that preserves the most future flexibility

The important part is not just choosing something that feels good. The important part is choosing a rule that is provably safe.

Greedy template

1. Define the choices
2. Choose a sorting or priority rule
3. Scan through choices
4. Take a choice if it does not break the solution
5. Return the final result

In this lesson, we will keep the reasoning beginner-friendly: if your choice leaves at least as many future options as any other choice, it is often a strong greedy candidate.

You are solving a problem and notice that choosing the item that finishes earliest always leaves the most remaining room for future items.

Which algorithmic strategy does this most strongly suggest?

Classic greedy example

Problem: given meetings with start and end times, attend the maximum number of non-overlapping meetings.

A tempting idea is to pick the shortest meeting or the earliest starting meeting. But the winning rule is:

Always pick the meeting that ends earliest among the meetings still available.

Why? The meeting that ends earliest leaves the largest remaining timeline for future meetings.

Example

Meetings:

(1, 4), (2, 3), (3, 5), (0, 7), (5, 8)

Pick (2, 3) first because it ends earliest. Then pick (3, 5), then (5, 8). That gives 3 meetings.

```python
from typing import List, Tuple

def max_non_overlapping_meetings(meetings: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
    meetings.sort(key=lambda meeting: meeting[1])  # sort by end time

    chosen = []
    current_end = float("-inf")

    for start, end in meetings:
        if start >= current_end:
            chosen.append((start, end))
            current_end = end

    return chosen

meetings = [(1, 4), (2, 3), (3, 5), (0, 7), (5, 8)]
answer = max_non_overlapping_meetings(meetings)
print(answer)
print("Maximum meetings:", len(answer))
```

For the meeting scheduling problem, the greedy strategy sorts meetings by their ____.

Greedy needs a reason

A greedy solution usually needs a short proof idea. You do not need formal math at first, but you do need a convincing explanation.

For interval scheduling, the proof intuition is an exchange argument:

1. Imagine an optimal solution that does not pick the earliest-ending meeting.
2. Replace its first meeting with the earliest-ending meeting.
3. This replacement cannot reduce the number of future meetings, because the new meeting ends no later.
4. So there is still an optimal solution that starts with the greedy choice.

That means the first greedy choice is safe. Then the same logic repeats for the remaining timeline.

Interview-friendly wording

"I sort by end time because choosing the earliest finishing valid meeting leaves maximum room for the rest. Any optimal solution can swap its first selected meeting with this one without hurting the answer."

True or false: If a greedy algorithm passes several sample test cases, then the greedy rule is guaranteed to be correct.

Greedy with reachability

Problem: given an array where nums[i] is the maximum jump length from index i, decide if you can reach the last index.

Example:

nums = [2, 3, 1, 1, 4]

From index 0, you can reach up to index 2. As you scan, keep the farthest reachable index seen so far.

Greedy rule:

If the current index is reachable, update the farthest place we can reach.

If we ever stand on an index beyond our farthest reach, we are stuck.

```python
def can_jump(nums):
    farthest = 0

    for i, jump in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + jump)

        if farthest >= len(nums) - 1:
            return True

    return True

print(can_jump([2, 3, 1, 1, 4]))  # True
print(can_jump([3, 2, 1, 0, 4]))  # False
```

How to choose

Greedy and DP both often solve optimization problems, but they feel different.

DP asks

• What are the smaller states?
• How do states transition?
• What answers should I store?

Greedy asks

• What is the next safest choice?
• What ordering makes that choice obvious?
• Why will I never need to undo it?

Quick comparison

Situation Often suggests Overlapping subproblems DP Need best answer for many states DP One local choice preserves future options Greedy Sorting reveals a safe order Greedy

A useful habit: if greedy feels possible, test it hard. If you cannot explain why the choice is safe, consider DP or backtracking.

Counterexample: coin change

Greedy can fail when the local best choice blocks the global best answer.

Suppose you want to make amount 6 using coins [1, 3, 4].

Greedy picks the largest coin first:

4 + 1 + 1 = 3 coins

But the optimal answer is:

3 + 3 = 2 coins

This is why the previous lesson on DP still matters. Some problems that look greedy need DP instead.

```python
def greedy_coin_count(coins, amount):
    coins = sorted(coins, reverse=True)
    count = 0
    remaining = amount

    for coin in coins:
        while remaining >= coin:
            remaining -= coin
            count += 1

    return count if remaining == 0 else -1

coins = [1, 3, 4]
amount = 6
print("Greedy coin count:", greedy_coin_count(coins, amount))
print("Optimal would be 2 coins: 3 + 3")
```

What to practice today

Greedy skill comes from pairing implementation with explanation. For each problem, write one sentence explaining why the local choice is safe.

Add these to your 2-day revisit queue

• Assign Cookies
• Best Time to Buy and Sell Stock
• Maximum Subarray
• Jump Game
• Non-overlapping Intervals
• Minimum Number of Arrows to Burst Balloons

Your greedy checklist

1. What choices am I making?
2. Can I sort the choices?
3. What local rule am I using?
4. Why does that rule preserve future options?
5. Can I find a counterexample?
6. What is the time complexity?

Most beginner greedy solutions are short, but the reasoning is the real lesson. Next, we will move into Advanced Data Structures: Heaps and Hash Tables, which gives you more tools for organizing choices efficiently.