> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.
# Greedy Algorithms
> Master the art of making locally optimal choices that lead to globally optimal solutions
# Greedy Algorithms
## The Mental Model
Greedy is about **making the best choice at each step without looking back**. Imagine you're collecting coins scattered on a path—you pick up the highest value coin at each position. Sometimes this works perfectly; sometimes it fails spectacularly.
**Pattern Recognition Signals**:
* "Minimum number of operations/items"
* "Maximum value/count possible"
* Problem has **optimal substructure** + **greedy choice property**
* Sorting + processing often leads to answer
***
## When Greedy Works (and When It Doesn't)
* Local optimal leads to global optimal
* No need to reconsider past choices
* Exchange argument can prove correctness
* Problem has "greedy choice property"
* Current choice affects future options
* Need to try all possibilities (use DP)
* Counter-example exists
* Problem mentions "subsequence" (often DP)
***
## The Greedy Proof: Exchange Argument
To prove greedy works, show that **swapping from greedy to non-greedy never improves the answer**. This is the most common proof technique for greedy algorithms in competitive programming.
**The template**:
1. Assume an optimal solution O that differs from the greedy solution G
2. Find the first place where they differ
3. Show you can "exchange" O's choice for G's choice without making things worse
4. Repeat until O matches G -- proving G is also optimal
**Example**: Activity Selection (select max non-overlapping intervals)
**Greedy**: Always pick the interval that ends earliest.
**Proof**: Suppose optimal solution picks interval A instead of greedy's choice B (where B ends earlier). Replace A with B. Since B ends earlier, it cannot conflict with anything A did not conflict with. So we still have a valid solution with at least as many intervals. By repeating this exchange, we can transform the optimal solution into the greedy solution without losing any intervals.
**Contest tip**: You do not need to write a formal proof during a contest. But you should mentally verify the exchange argument in 30 seconds. If you cannot convince yourself that swapping is safe, the greedy is probably wrong--consider DP instead.
***
## Pattern 1: Interval Scheduling
**Problem**: Select maximum number of non-overlapping intervals.
**Greedy Strategy**: Sort by end time, always pick next non-overlapping.
```cpp theme={null}
int maxNonOverlapping(vector>& intervals) {
// Sort by end time
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
return a.second < b.second;
});
int count = 0, lastEnd = INT_MIN;
for (auto& [start, end] : intervals) {
if (start >= lastEnd) {
count++;
lastEnd = end;
}
}
return count;
}
```
**Why End Time?**: An interval that ends early leaves more room for future intervals.
**Codeforces Problems**:
| Problem | Rating | Link |
| --------------- | ------ | ---------------------------------------------------------- |
| Classroom Watch | 1200 | [CF 875A](https://codeforces.com/problemset/problem/875/A) |
| Movie Festival | - | [CSES](https://cses.fi/problemset/task/1629) |
***
## Pattern 2: Task Scheduling with Deadlines
**Problem**: Tasks have deadlines and durations. Minimize lateness.
**Greedy Strategy**: Sort by deadline (Earliest Deadline First).
```cpp theme={null}
int minLateness(vector>& tasks) { // {duration, deadline}
sort(tasks.begin(), tasks.end(), [](auto& a, auto& b) {
return a.second < b.second; // Sort by deadline
});
int time = 0, maxLate = 0;
for (auto& [duration, deadline] : tasks) {
time += duration;
maxLate = max(maxLate, time - deadline);
}
return maxLate;
}
```
***
## Pattern 3: Fractional Knapsack
**Problem**: Items have weight and value. Maximize value in capacity W. Can take fractions.
**Greedy Strategy**: Sort by value/weight ratio (value per unit weight), take as much as possible of the best items first.
**Why this works**: Since we can take fractions, there is no penalty for "partially using" an item. The optimal strategy is to always take the item giving you the most value per kilogram.
```cpp theme={null}
double fractionalKnapsack(vector>& items, int W) {
// Sort by value/weight ratio descending -- most valuable per unit first
sort(items.begin(), items.end(), [](auto& a, auto& b) {
return (double)a.second / a.first > (double)b.second / b.first;
});
double totalValue = 0;
for (auto& [weight, value] : items) {
if (W >= weight) {
W -= weight;
totalValue += value;
} else {
totalValue += (double)W / weight * value;
break;
}
}
return totalValue;
}
```
**0/1 Knapsack**: If you can't take fractions, greedy fails. Use DP instead.
***
## Pattern 4: Huffman Encoding (Min Cost Merging)
**Problem**: Merge elements repeatedly, cost = sum of merged elements. Minimize total cost.
**Greedy Strategy**: Always merge the two smallest.
**Why the two smallest?** Every element's value gets "re-paid" at every merge it participates in. Elements merged later participate in fewer future merges. So putting the largest elements into late merges (few future payments) and smallest into early merges (many future payments) minimizes total cost.
**Worked Example**: arr = \[1, 2, 3, 4]
* Merge 1 + 2 = 3, cost = 3. Array: \[3, 3, 4]
* Merge 3 + 3 = 6, cost = 6. Array: \[4, 6]
* Merge 4 + 6 = 10, cost = 10. Array: \[10]
* Total cost = 3 + 6 + 10 = 19
If instead we merged largest first: 3+4=7 (cost 7), 2+7=9 (cost 9), 1+9=10 (cost 10). Total = 26. Worse.
```cpp theme={null}
long long minMergeCost(vector& arr) {
// Min-heap: always access the two smallest elements
priority_queue, greater> pq(arr.begin(), arr.end());
long long totalCost = 0;
while (pq.size() > 1) {
long long a = pq.top(); pq.pop(); // Smallest
long long b = pq.top(); pq.pop(); // Second smallest
totalCost += a + b; // Pay the merge cost
pq.push(a + b); // Merged element goes back into the heap
}
return totalCost;
}
// Time: O(n log n) -- n-1 merges, each with O(log n) heap operations
```
***
## Pattern 5: Jump Game
**Problem**: Can you reach the last index? arr\[i] = max jump from i.
**Greedy Strategy**: Track the farthest position reachable.
**Analogy**: Imagine you are walking along a number line. At each position, you see how far ahead you could leap. You do not actually need to jump at every position -- you just keep track of the farthest point any position so far could reach. If at any position i you find you could never have gotten there (i > maxReach), the answer is "no."
```cpp theme={null}
bool canJump(vector& nums) {
int maxReach = 0; // The farthest index we can reach so far
for (int i = 0; i < nums.size(); i++) {
if (i > maxReach) return false; // Can't reach position i at all
maxReach = max(maxReach, i + nums[i]); // Extend our reach
}
return true; // maxReach >= n-1
}
// Minimum jumps to reach end (BFS-like greedy)
// Think of it as BFS levels: each "jump" covers a range of positions
int minJumps(vector& nums) {
int jumps = 0, currentEnd = 0, farthest = 0;
for (int i = 0; i < nums.size() - 1; i++) {
farthest = max(farthest, i + nums[i]); // Farthest reach from current level
if (i == currentEnd) { // Exhausted current jump's range
jumps++; // Must take another jump
currentEnd = farthest; // New range boundary
// If currentEnd >= n-1, we will reach the end
}
}
return jumps;
}
// Worked example: nums = [2, 3, 1, 1, 4]
// i=0: farthest=2, i==currentEnd(0) -> jumps=1, currentEnd=2
// i=1: farthest=4, i!=2
// i=2: farthest=4, i==currentEnd(2) -> jumps=2, currentEnd=4
// Answer: 2 jumps (0->1->4)
```
***
## Pattern 6: Gas Station
**Problem**: Circular route with gas stations. Find starting point to complete circuit.
**Greedy Insight**: If total gas >= total cost, a solution exists. Start from the point where running sum is minimum.
**Why this works**: If the tank drops below 0 at station i, no station from the current `start` through `i` can be the answer (they would all run out of gas at or before i). So we reset and try starting from `i + 1`. If the total gas is sufficient globally, the last reset point is guaranteed to work.
**Edge case**: If all gas\[i] == cost\[i], the answer is 0 (any starting point works since the tank never goes negative). If total gas \< total cost, no starting point works.
```cpp theme={null}
int canCompleteCircuit(vector& gas, vector& cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.size(); i++) {
int diff = gas[i] - cost[i]; // Net gas gain at station i
total += diff; // Track global gas balance
tank += diff; // Track current attempt's gas balance
if (tank < 0) {
start = i + 1; // Can't start from any station [start..i]
tank = 0; // Reset tank for new starting attempt
}
}
return total >= 0 ? start : -1; // -1 if total gas < total cost
}
```
***
## Common Greedy Mistakes
**Mistake 1: Assuming Greedy Without Proof**
Always verify with edge cases or construct a counter-example:
```
Greedy for 0/1 Knapsack?
Items: [(5, 10), (4, 40), (6, 30)] // (weight, value)
Capacity: 10
Greedy by ratio: take (4, 40) then can't fit rest
Value = 40
Optimal: take (4, 40) and (6, 30) doesn't fit...
Wait, take (5, 10) and... no
Actually take (4, 40): W=6 left, take nothing else = 40
Or take (5, 10) and nothing else = 10
Or take (6, 30) and (4, 40) = doesn't fit
Actually optimal is 40 + 30 if we could fit (6)... can't.
Greedy works here, but in general 0/1 knapsack needs DP.
```
**Mistake 2: Wrong Sorting Criteria**
Small changes in sort order can break greedy:
```cpp theme={null}
// WRONG for interval scheduling
sort(intervals.begin(), intervals.end()); // Sorts by start time
// CORRECT
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
return a.second < b.second; // Sort by END time
});
```
**Mistake 3: Greedy When DP Needed**
Signals that greedy fails:
* "Longest increasing **subsequence**" (not subarray)
* "Number of ways"
* Choices affect future options
* Classic problem known to need DP
***
## The Greedy Decision Flowchart
```
Can you sort the input?
├── Yes → After sorting, can you process greedily?
│ ├── Yes → Try to prove with exchange argument
│ │ ├── Proof works → Use greedy
│ │ └── Can't prove → Test edge cases, maybe DP
│ └── No clear greedy order → Likely DP or other
└── No → Is there a single pass greedy?
├── Yes → Track running max/min/sum
└── No → Probably not greedy
```
***
## Practice Problems
### Beginner (800-1100)
| Problem | Pattern | Link |
| ----------------- | --------------- | ---------------------------------------------------------- |
| Watermelon | Simple greedy | [CF 4A](https://codeforces.com/problemset/problem/4/A) |
| Team | Counting greedy | [CF 231A](https://codeforces.com/problemset/problem/231/A) |
| Petya and Strings | Comparison | [CF 112A](https://codeforces.com/problemset/problem/112/A) |
### Intermediate (1100-1400)
| Problem | Pattern | Link |
| --------------- | ------------------- | ------------------------------------------------------------ |
| Minimum Penalty | Sorting + greedy | [CF 1409C](https://codeforces.com/problemset/problem/1409/C) |
| Maximum Swap | Local greedy | [LeetCode 670](https://leetcode.com/problems/maximum-swap/) |
| Tasks | Interval scheduling | [CF 978F](https://codeforces.com/problemset/problem/978/F) |
### Advanced (1400-1700)
| Problem | Pattern | Link |
| --------------- | ----------------- | ------------------------------------------------------------ |
| Wi-Fi | Interval coverage | [CF 1216C](https://codeforces.com/problemset/problem/1216/C) |
| Hard Problem | Sorting + greedy | [CF 706C](https://codeforces.com/problemset/problem/706/C) |
| Array Splitting | Greedy selection | [CF 1175B](https://codeforces.com/problemset/problem/1175/B) |
***
## Key Takeaways
Prove greedy by showing swaps don't help.
Most greedy solutions start with sorting.
Greedy intuition can be wrong. Test edge cases.
"Subsequence" and "count ways" usually need DP.
***
## Next Up
Learn to split problems in half, solve each part, and combine results efficiently.