# Greedy — Data Structures & Algorithms

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

> Take the best-looking choice at each step and never reconsider.

## 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
- [x] 2 coins (3 + 3)
- [ ] Impossible

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