codaBack to Academy
patterns
Greedy Algorithms
Greedy algorithms make the locally optimal choice at each step, hoping to find the global optimum. Unlike dynamic programming, greedy approaches never reconsider previous choices. They work when the problem has the greedy-choice property (local optima lead to global optimum) and optimal substructure.
Use Cases
- •Activity selection and interval scheduling
- •Huffman coding for data compression
- •Minimum number of coins for change-making
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(n log n) | O(n log n) | O(n log n) |
| Space | O(n) | ||
Visualization
I0:(1, 4)
I1:(2, 3)
I2:(3, 5)
I3:(6, 8)
I4:(7, 9)
Implementation
Output
Click "Run Code" to see output...