# Greedy — Data Structures and Algorithms: Patterns for Interviews

Source: https://www.skillbyai.com/en/dsa/greedy

> Pick the locally best choice at each step, and learn when greedy works and when it fails, such as with coin change.

## Local optimum → global optimum?

A greedy algorithm commits to the locally best move (largest coin, earliest finishing meeting) and moves on. It only gives the right answer when the problem has the **greedy-choice property** — you must prove or test that.

## Interval scheduling

To fit the most non-overlapping intervals, always take the one that finishes earliest.

```python
def max_meetings(intervals):
    intervals.sort(key=lambda x: x[1])   # by end time
    count, end = 0, float('-inf')
    for s, e in intervals:
        if s >= end:
            count += 1
            end = e
    return count
```

**Quiz:** Coins [1, 3, 4], make 6 with fewest coins. Greedy (take 4 first) gives 3 coins (4+1+1). Optimal is...

- [ ] 3 coins — greedy is right
- [ ] Impossible
- [x] 2 coins (3 + 3)
- [ ] 1 coin

*Answer:* 2 coins (3 + 3). 3+3 = 6 uses two coins. Greedy fails here — coin change needs DP in general.