Greedy Algorithms
ב-Facebook Preparation meetup בתל אביב, 2023: "Assign cookies to children. Each child i has greed factor g[i], each cookie j has size s[j]. Assign each child at most one cookie that satisfies g[i] <= s[j]. Maximize number of content children." מועמד שניסה DP - 30 דקות ואז Timeout. מועמד שהבין Greedy - 5 שורות, O(n log n), ועבר.
Greedy הוא ה-Pattern שהכי קשה לזהות ב-First Glance. שאלות Greedy לא מגיעות עם תווית "use greedy here." הן מגיעות עם תיאור בעיה שנראה כמו DP, ורק לאחר ניתוח מוכיחים שה-Local Optimal הוא גם Global Optimal. זה הופך את הזיהוי לאתגר אמיתי.
Greedy הוא אחת הגישות שהכי קשה לדעת מתי להשתמש. השאלה תמיד היא: "האם ה-Local Optimum הוא גם ה-Global Optimum?" אם כן - Greedy. אם לא - DP.