Notes › DSA
Greedy Algorithms
A greedy algorithm makes the locally best choice at each step and never goes back. It is fast and simple — but it is only correct when the problem has the right structure.
When does greedy work?
- Greedy-choice property — a globally optimal answer can be reached by making the best local choice first.
- Optimal substructure — after that choice, the rest is a smaller problem of the same kind.
If you can find a counter-example where the local best choice loses, greedy is wrong → think DP.
Classic counter-example: coin change with coins {1, 3, 4} and amount 6. Greedy takes 4 + 1 + 1 (3 coins), but 3 + 3 (2 coins) is better. With Indian coins {1, 2, 5, 10} greedy works; for arbitrary coins, use DP.
Pattern 1: interval scheduling (activity selection)
Maximum number of non-overlapping meetings. Sort by end time, always take the meeting that ends first.
int maxMeetings(vector<pair<int,int>>& m) { // {start, end}
sort(m.begin(), m.end(), [](auto& a, auto& b) { return a.second < b.second; });
int count = 0, lastEnd = INT_MIN;
for (auto& [s, e] : m)
if (s >= lastEnd) { count++; lastEnd = e; }
return count;
}
Why it works: the meeting that ends earliest leaves the most room for the rest — an exchange argument shows swapping it into any optimal answer never makes things worse.
Related: non-overlapping intervals (remove the fewest = n − max kept), minimum arrows to burst balloons.
Pattern 2: merge intervals
Sort by start; extend the current interval while the next one overlaps.
vector<vector<int>> merge(vector<vector<int>>& iv) {
sort(iv.begin(), iv.end());
vector<vector<int>> res;
for (auto& x : iv) {
if (res.empty() || res.back()[1] < x[0]) res.push_back(x);
else res.back()[1] = max(res.back()[1], x[1]);
}
return res;
}
Pattern 3: jump game
Track the farthest index reachable so far.
bool canJump(vector<int>& a) {
int reach = 0;
for (int i = 0; i < a.size(); i++) {
if (i > reach) return false;
reach = max(reach, i + a[i]);
}
return true;
}
Jump game II (min jumps): BFS-like levels — count a jump each time you pass the end of the current range.
Pattern 4: fractional knapsack
Items can be broken, so take items by value/weight ratio, highest first. (The 0/1 knapsack, where items cannot be broken, needs DP.)
Pattern 5: two-pointer greedy
- Assign cookies: sort both; give the smallest cookie that satisfies the least greedy child.
- Boats to save people: sort; pair the heaviest with the lightest if they fit.
Pattern 6: minimum platforms / meeting rooms
Sort arrivals and departures separately; walk through them — +1 on arrival, −1 on departure; the maximum is the answer. (Or a min-heap of end times.)
Pattern 7: greedy with a heap
- Huffman coding: repeatedly merge the two lowest frequencies.
- Minimum cost to connect ropes, task scheduler, IPO.
- Dijkstra, Prim and Kruskal are greedy algorithms on graphs.
Proving a greedy solution (for interviews)
- Exchange argument: take any optimal solution; swap in the greedy choice; show it is still optimal.
- Stays ahead: after every step, greedy is at least as good as any other solution. Even one sentence of reasoning impresses interviewers.
Classic problems
| Problem | Greedy rule |
|---|---|
| N meetings in one room / activity selection | earliest end first |
| Merge intervals | sort by start |
| Non-overlapping intervals | earliest end first |
| Jump game I & II | farthest reach |
| Gas station | reset start when the tank goes negative |
| Minimum platforms | sweep arrivals/departures |
| Fractional knapsack | best value/weight first |
| Assign cookies / boats | sort + two pointers |
| Candy | two passes (left, right) |
Practise in the Greedy section.
Interview one-liners
- Greedy is usually sort + one pass → O(n log n).
- Always test greedy against small tricky cases before committing.
- If greedy fails, DP is the usual fix (coin change, 0/1 knapsack).