# Greedy — डेटा स्ट्रक्चर और एल्गोरिदम

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

> हर चरण पर सबसे अच्छा दिखने वाला चुनाव लें और फिर कभी पुनर्विचार न करें।

## स्थानीय इष्टतम → वैश्विक इष्टतम?

Greedy एल्गोरिदम स्थानीय रूप से सर्वश्रेष्ठ चाल (सबसे बड़ा सिक्का, सबसे पहले खत्म होने वाली मीटिंग) चुनकर आगे बढ़ता है। यह सही उत्तर तभी देता है जब समस्या में **greedy-choice गुण** हो — इसे सिद्ध या परखना ज़रूरी है।

## Interval scheduling

सबसे अधिक गैर-अतिव्यापी interval फ़िट करने के लिए, हमेशा वह लें जो सबसे पहले खत्म हो।

```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:** सिक्के [1, 3, 4], 6 बनाएँ कम से कम सिक्कों में। Greedy (पहले 4) 3 सिक्के देता है (4+1+1)। इष्टतम है...

- [ ] 3 सिक्के — greedy सही है
- [x] 2 सिक्के (3 + 3)
- [ ] असंभव

*Answer:* 2 सिक्के (3 + 3). 3+3 = 6 दो सिक्के उपयोग करता है। यहाँ greedy विफल — coin change को सामान्यतः DP चाहिए।