Greedy
Builds the solution step by step by always choosing the best option available at each moment.
The Approach
- Identify a greedy choice: a locally optimal decision that seems best at the current step.
- Prove (or assume) that making this greedy choice will lead to a globally optimal solution.
- Repeatedly make the greedy choice until the problem is solved.
- Often involves sorting the input to make the greedy choice easier to determine.
Types of Greedy
Interval Scheduling
Sort intervals by end times and pick the next non-overlapping interval.
[1, 4]
[3, 5]
[0, 6]
[5, 7]
[8, 9]
[5, 9]
Sort intervals by end time.
Optimal Substructure
The optimal solution to the problem contains optimal solutions to its subproblems.
[1, 4]
[3, 5]
[0, 6]
[5, 7]
[8, 9]
[5, 9]
Sort intervals by end time.
Common Problems
Merge Intervals
Greedy + Sorting
Maximum Subarray
Greedy
Jump Game
Greedy
Gas Station
Greedy
Partition Labels
Greedy
Non Overlapping Intervals
Greedy