Greedy

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

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

Interval scheduling

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

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

त्वरित जाँच: सिक्के [1, 3, 4], 6 बनाएँ कम से कम सिक्कों में। Greedy (पहले 4) 3 सिक्के देता है (4+1+1)। इष्टतम है...

• 3 सिक्के — greedy सही है
• असंभव
• 2 सिक्के (3 + 3)
• 1 coin