DSA Patterns
Greedy Algorithms
Master the technique of making locally optimal choices to achieve global optimization
Greedy Algorithms Pattern
A greedy algorithm makes the locally optimal choice at each step, hoping to find a global optimum. While not always yielding the best solution, greedy algorithms are often simple to implement and can be surprisingly effective.
Understanding Greedy Algorithms
What Makes an Algorithm Greedy?
- Local Optimization: Makes best possible choice at each step
- No Looking Back: Never reconsiders previous choices
- No Looking Ahead: Doesn’t plan for future steps
- Hope for the Best: Assumes local optima lead to global optimum
When to Use Greedy?
An algorithm can be greedy when the problem has:
- Greedy Choice Property: Local optimal choices lead to global optimal solution
- Optimal Substructure: Optimal solution contains optimal solutions to subproblems
- No Future Impact: Current choices don’t negatively affect future choices
Understanding Through Examples
1. Meeting Room Scheduling
Imagine you’re managing meeting room bookings. You have multiple meeting requests, each with a start and end time. You want to accommodate as many meetings as possible in a single room.
def maxMeetings(start: List[int], end: List[int]) -> int:
"""
Real-world scenario:
Time slots: [(9,10), (9,11), (10,12), (11,12), (12,13)]
Thought process:
1. Why sort by end time?
- Earlier ending meetings free up room sooner
- More opportunities for later meetings
2. Step-by-step decision making:
(9,10) → Accept (ends earliest)
(9,11) → Reject (overlaps with accepted)
(10,12) → Reject (overlaps)
(11,12) → Accept (starts after 10)
(12,13) → Accept (starts after 12)
Result: 3 meetings possible [(9,10), (11,12), (12,13)]
"""
meetings = sorted(zip(start, end), key=lambda x: x[1])
count = 1 # First meeting always gets scheduled
last_end = meetings[0][1]
for i in range(1, len(meetings)):
if meetings[i][0] >= last_end:
count += 1
last_end = meetings[i][1]
return count
2. Task Scheduling with Deadlines
Consider a scenario where each task has a duration and deadline. You need to schedule tasks to maximize the number of tasks completed before their deadlines.
Visual Example:
Tasks: [(2,4), (1,3), (3,6), (2,3)]
(duration, deadline)
Timeline visualization:
0 1 2 3 4 5 6
│ │ │ │ │ │ │
Task2(1,3)───┤
Task1(2,4)───────┤
Task4(2,3)X │ // Missed deadline
Task3(3,6)─────────┤
Decision Process:
1. Sort by deadline (and duration for ties)
2. Schedule earliest deadline first if possible
3. Skip if can't meet deadline
Understanding Greedy Choice Property
Let’s break down why greedy works (or doesn’t) through examples:
- Successful Greedy: Platform Assignment
"""
Problem: Find minimum platforms needed for train schedule
Input: arrival[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
departure[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
Visual Timeline:
9:00 ──────╮
9:40 ────────────╮
9:50 ──────╮ │
11:00 ────╮│ │
15:00 ────────────────╮
18:00 ────────────────────╮
Why Greedy Works Here:
1. Each time point is independent
2. Only care about current platform count
3. Past decisions don't affect future options
4. Can process events in time order
"""
def minPlatforms(arrivals: List[int], departures: List[int]) -> int:
events = [(t, 1) for t in arrivals] + [(t, -1) for t in departures]
events.sort() # Sort by time
platforms = max_platforms = 0
for time, change in events:
platforms += change
max_platforms = max(max_platforms, platforms)
return max_platforms
- Failed Greedy: Job Scheduling with Dependencies
"""
Problem: Schedule jobs with dependencies to minimize completion time
Jobs: A, B, C, D
Dependencies: A→B, B→C, A→D
Duration: A(2), B(1), C(2), D(1)
Greedy Approach (fails):
1. Pick shortest available job
2. Schedule when dependencies met
Why It Fails:
┌─── A(2) ───┐
├─── B(1) ───┐
└─── D(1) ├─── C(2)
│
Better Solution:
┌─── A(2) ───┐
├─── B(1) ───┐
├─── C(2)
└────── D(1) ┘
Lesson: Local decisions (picking shortest)
don't account for global structure (critical path)
"""
Advanced Greedy Concepts
- Exchange Arguments This is a technique to prove greedy algorithms correct:
Example: Activity Selection
Proof sketch:
1. Take optimal solution S
2. If S doesn't start with earliest-ending activity A:
- Remove first activity B from S
- Replace with A
- New solution is still valid (A ends earlier)
- Therefore, optimal solution must start with A
3. Repeat for remaining subproblem
- Matroid Theory Some greedy problems are based on matroid properties:
Examples of Matroids:
1. Spanning Tree Selection
- Elements: Edges of graph
- Independent sets: Acyclic edge sets
2. Task Scheduling
- Elements: Tasks
- Independent sets: Non-overlapping task sets
Why Important:
- Guarantees greedy algorithm optimality
- Helps identify when greedy will work
Classic Examples with Explanations
-
Coin Change (With Denominations [1, 5, 10, 25])
def minCoins(amount: int) -> int: """ Greedy works here because: 1. Larger coins are multiples of smaller ones 2. We can always use larger coins first Example: amount = 67 Step 1: Use 25s → 67 = 25 + 25 + 17 (2 coins) Step 2: Use 10s → 17 = 10 + 7 (1 coin) Step 3: Use 5s → 7 = 5 + 2 (1 coin) Step 4: Use 1s → 2 = 1 + 1 (2 coins) Total: 6 coins (25, 25, 10, 5, 1, 1) """ coins = [25, 10, 5, 1] count = 0 for coin in coins: while amount >= coin: amount -= coin count += 1 return count -
Activity Selection
def maxActivities(start: List[int], end: List[int]) -> List[int]: """ Problem: Select maximum number of non-overlapping activities Why Greedy Works: - Selecting earliest finishing activity maximizes remaining time - Remaining subproblem has same structure Example: Activities: [(1,4), (2,5), (3,6), (5,7), (8,9)] Step 1: Sort by end time Step 2: Pick first activity (1,4) Step 3: Skip activities overlapping with (1,4) Step 4: Pick next non-overlapping (5,7) Step 5: Pick next non-overlapping (8,9) Result: [(1,4), (5,7), (8,9)] """ # Sort activities by end time activities = sorted(zip(start, end), key=lambda x: x[1]) selected = [activities[0]] last_end = activities[0][1] for start_time, end_time in activities[1:]: if start_time >= last_end: selected.append((start_time, end_time)) last_end = end_time return selected
Common Greedy Strategies
-
Sort First
""" Many greedy problems become easier after sorting: - Sort by end time (Activity Selection) - Sort by value/weight ratio (Fractional Knapsack) - Sort by deadline (Job Scheduling) Why? Sorting often reveals optimal order for decisions """ -
Take Maximum/Minimum
""" Strategy: Always choose the best available option Examples: 1. Huffman Coding - Always merge two nodes with minimum frequency 2. Prim's Algorithm - Always choose minimum weight edge 3. Dijkstra's Algorithm - Always choose vertex with minimum distance """ -
Forward/Backward Processing
""" Some problems are easier to solve in a specific direction Example: Task Scheduling Forward: Schedule tasks from earliest to latest - Good for deadline constraints - Better for resource allocation Backward: Schedule from latest to earliest - Good for dependency resolution - Better for just-in-time scheduling """
Real-World Applications
-
Network Design
def minimumSpanningTree(graph: List[List[int]]) -> int: """ Prim's Algorithm for MST Real-world uses: 1. Network cable routing 2. Pipeline construction 3. Circuit design 4. Road network planning Why Greedy Works: - Adding minimum edge at each step - Can't create cycles (suboptimal) - Connected components grow optimally """ # Implementation details... -
Resource Allocation
def jobScheduling(deadlines: List[int], profits: List[int]) -> int: """ Job Scheduling with Deadlines Applications: 1. CPU scheduling 2. Project management 3. Manufacturing planning 4. Cloud resource allocation Greedy Strategy: 1. Sort jobs by profit (highest first) 2. Schedule each job at latest possible time 3. Skip if no valid time slot """ # Implementation details...
When Greedy Fails
-
Global vs Local Optimum
""" Example: Coin Change with denominations [1, 3, 4] Amount = 6 Greedy Solution: 4 + 1 + 1 = 6 (3 coins) Optimal Solution: 3 + 3 = 6 (2 coins) Why Greedy Failed: - Local choice (using 4) prevented better global solution - Need to consider combinations, not just largest first """ -
Future Impact
""" Example: Knapsack Problem (0/1) Items: 1. Weight: 1, Value: 1 2. Weight: 2, Value: 5 3. Weight: 3, Value: 3 Capacity: 3 Greedy by value/weight: Choose item 2 (weight 2) → Can only add item 1 Total value: 6 Optimal: Choose items 1 and 3 Total value: 8 """
Practice Problems
-
Basic
- Fractional Knapsack
- Activity Selection
- Minimum Coins
- Huffman Coding
-
Intermediate
- Job Sequencing
- Minimum Platforms
- Maximum Meetings
- Gas Station
-
Advanced
- Task Scheduler
- Minimum Number of Arrows
- Queue Reconstruction
- Split Array into Consecutive Sequences
Remember: The key to mastering Greedy Algorithms is to:
- Identify if greedy approach is valid
- Prove greedy choice property
- Consider edge cases
- Test with counter-examples
- Understand when greedy might fail
Articles & Tutorials
Visualizations
Visualizer not available for this pattern yet. We're working on it!