Greedy Algorithms

Greedy Algorithms

Now that we've covered Dynamic Programming, Recursion and Backtracking, and Hashing and Hash Tables, you're ready for a different interview move: making a smart choice right now and committing to it.

A greedy algorithm builds an answer step by step by repeatedly choosing the best-looking next option.

This matters in interviews because greedy solutions are often:

• Shorter to code than DP
• Faster in time and memory
• Common in scheduling, intervals, trading-style optimization, and resource allocation questions

The danger: greedy is not magic. A local best choice only works when that choice cannot hurt the global answer.

The Core Idea

A greedy algorithm says:

At each step, take the choice that looks best according to a rule, then never undo it.

That rule might be:

• Pick the meeting that ends earliest
• Pick the cheapest available option
• Pick the largest coin that fits
• Pick the most profitable next step

Compared with Backtracking, greedy does not explore many branches. Compared with Dynamic Programming, greedy does not keep a table of many possible states.

That is why greedy can be very fast — but only if the rule is correct.

Example: Attend Maximum Meetings

Suppose you have meeting intervals and want to attend as many non-overlapping meetings as possible.

A strong greedy rule is:

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

Why? Finishing earlier leaves the most room for future meetings.

This uses ideas you already saw in Sorting and Searching: we sort first to create useful structure, then scan once.

```python
def max_meetings(intervals):
    # Sort by end time: the meeting that frees us earliest comes first.
    intervals.sort(key=lambda x: x[1])

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

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

    return chosen

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

You are deciding whether a greedy approach might work for a problem.

Which signal is the strongest reason to try greedy?

Greedy Needs a Reason

In interviews, do not just say, "I will be greedy." Say why your greedy choice is safe.

For interval scheduling, the reasoning is:

1. We must choose some first meeting.
2. If an optimal answer starts with a meeting that ends later, we can swap in the earliest-ending compatible meeting.
3. This swap does not reduce the number of meetings we can attend.
4. After that choice, the remaining problem is the same kind of problem on the remaining timeline.

This is often called an exchange argument: show that an optimal solution can be adjusted to include your greedy choice.

The Coin Change Trap

A common beginner mistake is thinking:

If greedy feels natural, it must be optimal.

For some coin systems, picking the largest coin first works. For others, it fails.

Below, the coins are [4, 3, 1] and the amount is 6.

Greedy picks 4 + 1 + 1 = 3 coins.

But the optimal answer is 3 + 3 = 2 coins.

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

    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
            used.append(coin)

    return count, used

coins = [4, 3, 1]
amount = 6
count, used = greedy_coin_count(coins, amount)

print("Greedy coins used:", used)
print("Greedy coin count:", count)
print("Better answer exists: [3, 3] uses 2 coins")
```

True or false:

If a greedy algorithm passes the sample tests, then it is guaranteed to be optimal for all inputs.

For the maximum number of non-overlapping meetings problem, a common greedy strategy is to sort intervals by earliest ____.

Example: Add Every Gain

A useful interview-style greedy problem:

Given daily prices, find the maximum profit if you can buy and sell multiple times, but can hold only one share at a time.

Greedy idea:

Every time tomorrow's price is higher than today's, take that profit.

This works because a long upward run can be split into smaller daily gains without changing the total profit.

For example, buying at 1 and selling at 5 gives profit 4. Taking daily gains from 1→3 and 3→5 gives 2 + 2 = 4.

```python
def max_profit(prices):
    profit = 0

    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]

    return profit

prices = [7, 1, 3, 5, 4, 6]
print("Prices:", prices)
print("Max profit:", max_profit(prices))
```

Greedy Interview Checklist

When you suspect greedy, use this structure:

1. Define the goal: maximize count, minimize cost, maximize profit, etc.
2. Choose a greedy rule: earliest end, smallest cost, largest gain, shortest deadline.
3. Test small counterexamples: try to break your own rule.
4. Explain why it is safe: use an exchange argument or show the remaining problem has the same shape.
5. Analyze complexity: often sorting dominates, commonly O(n log n), followed by an O(n) scan.

For a financial-firm interview, the important part is not sounding fancy. It is showing disciplined decision-making: choose a rule, challenge it, justify it, then code it cleanly.

Next, we will move from single-algorithm problems toward broader engineering thinking in System Design Basics.