đ° Greedy Algorithms
Make locally optimal choices at each step to find global optimum. Master activity selection, Huffman coding, and more.
Overview
What are Greedy Algorithms?
Key Greedy Algorithms
Activity Selection
Select maximum non-overlapping activities from a set
Coin Change (Greedy)
Minimum coins with unlimited supply of denominations
Fractional Knapsack
Maximize value with fraction-allowed items
Huffman Coding
Build optimal prefix code for data compression
Job Sequencing
Schedule jobs with deadlines for maximum profit
Interactive Visualizer
Algorithm Visualization
Activity Selection Visualizer
Watch greedy decisions being made step by step to build the optimal solution.
Deep Dive: Activity Selection
Time Complexity
Time: O(n log n)Space Complexity
Space: O(1)Key Insight
Greedy Choice PropertyGreedy Strategy
python
def activitySelection(activities):
activities.sort(key=lambda x: x[1])
count = 1
end = activities[0][1]
for i in range(1, len(activities)):
if activities[i][0] >= end:
count += 1
end = activities[i][1]
return countSort/Candidates
Arrange possible choices in order based on some criterion.
Make Greedy Choice
Select the best immediate option from remaining candidates.
Check Feasibility
Verify the choice satisfies constraints and maintains correctness.
Repeat
Continue until solution is complete or no candidates remain.
Real-World Applications
Data Compression
Huffman coding creates optimal prefix codes for lossless compression
Network Routing
Dijkstra's algorithm greedily selects the closest unvisited vertex
Resource Allocation
CPU scheduling, memory allocation use greedy strategies
Minimum Spanning Trees
Prim's and Kruskal's algorithms build MSTs greedily
Optimization Problems
Traveling salesman, task scheduling, packing problems
Compression Algorithms
Run-length encoding, dictionary-based compression
Interview Questions
When should you use greedy vs DP?
Use greedy when the greedy choice property holds (local optimum â global optimum). Use DP when overlapping subproblems exist and greedy fails. Example: coin change with standard denominations works greedy; with arbitrary denominations, use DP.
What is the greedy choice property?
A globally optimal solution can be arrived at by making locally optimal (greedy) choices at each step. Once made, these choices are never reconsidered.
What is optimal substructure?
An optimal solution to the problem contains optimal solutions to subproblems. This property is shared by both greedy and DP problems.
Knowledge Check
1. What makes a problem suitable for greedy algorithms?
2. Does greedy always produce the optimal solution?
3. What is the time complexity of Activity Selection?
4. Why might greedy fail for coin change?
5. What data structure is key for Huffman coding?
Common Mistakes to Avoid
Assuming greedy always gives optimal solution - many problems need DP
Not verifying the greedy choice property - local optimum may not lead to global optimum
Forgetting to sort input first - most greedy algorithms require sorted data
Applying greedy to problems with constraints that require backtracking
Not testing with edge cases: empty input, single element, all same values