DSA Sheet - Day 33 Greedy
💡 DSA Sheet – Day 33: Greedy Algorithms
Greedy problems are all about making the best local choice that leads to a globally optimal solution. These are extremely common in coding interviews.
📊 Progress Tracker
Progress: 0 / 6 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| Assign Cookies | Solve | Easy | Google, Amazon | |
| Indian Coins (Min Coins) | Solve | Easy | Amazon | |
| Fractional Knapsack | Solve | Medium | Microsoft | |
| Job Scheduling (Max Profit) | Solve | Medium | Microsoft, Adobe | |
| Activity Selection | Solve | Medium | Amazon, Meta | |
| Maximum Length of Pair Chain | Solve | Medium |
🧠 Key Approaches
- Assign Cookies: Sort both arrays → satisfy smallest greed first
- Indian Coins: Always pick the largest denomination
- Fractional Knapsack: Sort by value/weight ratio
- Job Scheduling: Sort by profit → fill latest slot
- Activity Selection: Sort by end time → pick earliest finishing
- Pair Chain: Sort pairs → greedy OR LIS
⚡ Quick Cheatsheet
Fractional Knapsack
sort(items.begin(), items.end(), by value/weight descending);
Activity Selection
sort(intervals by end time);
pick next non-overlapping activity
Job Scheduling
sort(jobs by profit descending);
// assign job to latest available slot
Assign Cookies
sort(greed);
sort(size);
// match smallest possible cookie
🔥 Pro Tip
Greedy works when:
- Local optimal choice leads to global optimum
- Sorting simplifies decision making
- No need to revisit previous choices