14.23 Case Studies
Greedy algorithms become easier to recognize after seeing them embedded in complete problems.
14.23 Case Studies
Greedy algorithms become easier to recognize after seeing them embedded in complete problems. A textbook description often isolates the core idea, but real use cases include input modeling, edge cases, implementation constraints, and proof obligations.
This recipe walks through several compact case studies. Each one follows the same structure:
Model the problem.
Identify the greedy choice.
Choose the supporting data structure.
Prove why the choice is safe.
Analyze complexity.
The goal is not to introduce entirely new theory. The goal is to show how the chapter’s patterns combine in practical algorithm design.
Case Study 1: Meeting Room Allocation
Suppose you are given meeting intervals and need to compute the minimum number of rooms required.
Input:
[0, 30], [5, 10], [15, 20]
Output:
2
The problem is not asking which meetings to keep. All meetings must be scheduled. The only question is how many resources are needed.
Greedy Choice
Process meetings by start time.
When a meeting starts:
- If the earliest-ending room is free, reuse it.
- Otherwise allocate a new room.
The greedy rule is:
Reuse the room that becomes available earliest.
This preserves maximum flexibility for later meetings.
Data Structure
Use a min-heap of room end times.
The heap top is the room that frees first.
type MinHeap []int
func (h MinHeap) Len() int {
return len(h)
}
func (h MinHeap) Less(i, j int) bool {
return h[i] < h[j]
}
func (h MinHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *MinHeap) Push(x any) {
*h = append(*h, x.(int))
}
func (h *MinHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
Implementation:
type Meeting struct {
Start int
End int
}
func MinMeetingRooms(meetings []Meeting) int {
if len(meetings) == 0 {
return 0
}
sort.Slice(meetings, func(i, j int) bool {
return meetings[i].Start < meetings[j].Start
})
h := &MinHeap{}
heap.Init(h)
for _, meeting := range meetings {
if h.Len() > 0 && (*h)[0] <= meeting.Start {
heap.Pop(h)
}
heap.Push(h, meeting.End)
}
return h.Len()
}
Correctness
At each meeting start, the only reusable room that matters first is the room with the earliest end time.
If that room is not free, no other room is free either.
If that room is free, reusing it cannot hurt future choices because it is the resource that has been idle longest relative to the current start.
The heap maintains exactly the active rooms, so its size after processing all meetings is the maximum number of simultaneous meetings.
Complexity
Sorting costs:
O(n log n)
Each meeting is pushed once and popped at most once:
O(n log n)
Total:
O(n log n)
Space:
O(n)
Case Study 2: Reorganizing a String
Given a string, rearrange it so that no two adjacent characters are equal. If impossible, return an empty string.
Example:
aaabbc
Possible output:
ababac
This is a string problem, but the greedy pattern is priority-queue based.
Greedy Choice
At each step, place the character with the highest remaining frequency that is not equal to the previously placed character.
Why highest frequency?
Because the most frequent character is the most dangerous one. If it is postponed too long, it may become impossible to separate its copies.
Data Structure
Use a max-heap keyed by remaining count.
type CharCount struct {
Ch byte
Count int
}
type MaxHeap []CharCount
func (h MaxHeap) Len() int {
return len(h)
}
func (h MaxHeap) Less(i, j int) bool {
return h[i].Count > h[j].Count
}
func (h MaxHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *MaxHeap) Push(x any) {
*h = append(*h, x.(CharCount))
}
func (h *MaxHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
Implementation:
func ReorganizeString(s string) string {
count := make([]int, 26)
for i := 0; i < len(s); i++ {
count[s[i]-'a']++
}
h := &MaxHeap{}
heap.Init(h)
for i := 0; i < 26; i++ {
if count[i] > 0 {
heap.Push(h, CharCount{
Ch: byte('a' + i),
Count: count[i],
})
}
}
result := make([]byte, 0, len(s))
for h.Len() >= 2 {
first := heap.Pop(h).(CharCount)
second := heap.Pop(h).(CharCount)
result = append(result, first.Ch)
result = append(result, second.Ch)
first.Count--
second.Count--
if first.Count > 0 {
heap.Push(h, first)
}
if second.Count > 0 {
heap.Push(h, second)
}
}
if h.Len() == 1 {
last := heap.Pop(h).(CharCount)
if last.Count > 1 {
return ""
}
if len(result) > 0 && result[len(result)-1] == last.Ch {
return ""
}
result = append(result, last.Ch)
}
return string(result)
}
Correctness
The algorithm always takes the two most frequent remaining distinct characters.
This avoids placing equal adjacent characters and reduces the most constrained resources first. If a character count ever exceeds what the remaining positions can separate, no valid arrangement exists.
A common impossibility condition is:
max frequency > ceil(n / 2)
The heap algorithm detects this through the final leftover check.
Complexity
For a fixed lowercase alphabet:
O(n)
because the heap has at most 26 elements.
For a general alphabet of size σ:
O(n log σ)
Space:
O(σ)
Case Study 3: Maximum Units on a Truck
You have box types. Each type has a number of boxes and units per box. A truck can carry at most truckSize boxes. Maximize total units loaded.
Input:
boxTypes = [[1,3], [2,2], [3,1]]
truckSize = 4
Output:
8
Explanation:
1 box with 3 units
2 boxes with 2 units each
1 box with 1 unit
Total:
3 + 4 + 1 = 8
Greedy Choice
Always load boxes with the most units per box first.
This is the same structure as fractional knapsack, except boxes are discrete and all boxes consume the same capacity unit.
Because each box costs exactly one truck slot, choosing the highest units-per-box item is always safe.
Implementation
type BoxType struct {
Count int
Units int
}
func MaximumUnits(boxTypes []BoxType, truckSize int) int {
sort.Slice(boxTypes, func(i, j int) bool {
return boxTypes[i].Units > boxTypes[j].Units
})
total := 0
for _, box := range boxTypes {
if truckSize == 0 {
break
}
take := box.Count
if take > truckSize {
take = truckSize
}
total += take * box.Units
truckSize -= take
}
return total
}
Correctness
Suppose a solution uses a box with fewer units while a higher-unit box remains unloaded.
Exchange the lower-unit box with the higher-unit box.
Capacity usage remains unchanged because both consume one slot.
Total units increase or stay equal.
Therefore an optimal solution exists that loads higher-unit boxes first.
Complexity
Sorting:
O(n log n)
Scan:
O(n)
Total:
O(n log n)
Space:
O(1)
excluding sort internals.
Case Study 4: Minimum Number of Platforms
Given arrival and departure times of trains, find the minimum number of platforms required so no train waits.
Arrivals:
900, 940, 950, 1100, 1500, 1800
Departures:
910, 1200, 1120, 1130, 1900, 2000
Output:
3
Greedy Choice
Process all arrival and departure events in chronological order.
- Arrival increases active trains.
- Departure decreases active trains.
- Maximum active count is the number of platforms needed.
This is a sweep-line greedy pattern.
Implementation
func MinPlatforms(arr []int, dep []int) int {
sort.Ints(arr)
sort.Ints(dep)
i := 0
j := 0
active := 0
answer := 0
for i < len(arr) && j < len(dep) {
if arr[i] <= dep[j] {
active++
if active > answer {
answer = active
}
i++
} else {
active--
j++
}
}
return answer
}
Correctness
At any time, the number of platforms required equals the number of trains currently present.
Processing events in chronological order maintains that active count exactly.
The maximum active count over the scan is the minimum number of platforms needed, because at that instant all active trains require distinct platforms.
Complexity
Sorting arrivals and departures:
O(n log n)
Sweep:
O(n)
Total:
O(n log n)
Space:
O(1)
excluding sorting workspace.
Case Study 5: Lemonade Change
Customers queue to buy lemonade costing 5. Each customer pays with 5, 10, or 20. Determine whether correct change can be given to every customer.
Input:
5, 5, 5, 10, 20
Output:
true
Greedy Choice
When a customer pays with 20, change required is 15.
There are two possible ways:
10 + 5
or
5 + 5 + 5
The greedy rule is:
Use one 10 and one 5 if possible.
Why?
Because 5-dollar bills are more flexible. They are needed for both 10-dollar and 20-dollar payments. Preserving them is valuable.
Implementation
func LemonadeChange(bills []int) bool {
five := 0
ten := 0
for _, bill := range bills {
switch bill {
case 5:
five++
case 10:
if five == 0 {
return false
}
five--
ten++
case 20:
if ten > 0 && five > 0 {
ten--
five--
} else if five >= 3 {
five -= 3
} else {
return false
}
}
}
return true
}
Correctness
For a 20-dollar bill, using 10 + 5 preserves more 5-dollar bills than using three 5-dollar bills.
Since 5-dollar bills are required for every change-making operation, preserving them cannot make future transactions worse.
This is a small but clean greedy exchange argument.
Complexity
Single scan:
O(n)
Space:
O(1)
Lessons from the Case Studies
These examples use different surface structures:
| Case Study | Greedy Pattern |
|---|---|
| Meeting rooms | Min-heap resource reuse |
| Reorganize string | Max-heap frequency control |
| Truck loading | Sort by value density |
| Train platforms | Sweep-line active count |
| Lemonade change | Preserve flexible resource |
The common design method remains the same:
Identify the scarce resource.
Choose the action that preserves future feasibility.
Use the simplest structure that supports the choice.
Prove that no better solution is excluded.
Takeaway
Greedy case studies show that implementation details vary, but the reasoning pattern is stable. Meeting rooms reuse the earliest available resource; string reorganization reduces the most constrained character counts; truck loading prioritizes the most valuable unit capacity; platform allocation tracks maximum simultaneous demand; lemonade change preserves the most flexible bills. Each algorithm succeeds because its local decision preserves or improves the future state without excluding an optimal solution.