Where it runs
1. The problem
You have one meeting room and a pile of booking requests. Each request has a start time and an end time. Some requests overlap: a booking from 9 to 11 and one from 10 to 12 cannot both get the room. You want to accept as many requests as you can, without ever booking the room twice at the same time.
A billboard with one screen and a list of ad slots works the same way, and so does one machine with a queue of jobs. There is one resource and many requests, each with its own time, and you want to handle as many of them as possible.
The most obvious rules lose. Take the requests [0,30], [5,10], [15,20]. If you take the one that starts first, you take [0,30], and it blocks both others: one meeting instead of two. Taking the shortest one can also go wrong: of [1,5], [4,7], [6,10] the shortest is [4,7], and it overlaps both its neighbours. Exactly one rule always works, and this lesson is about it.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- fewest coins or pieces to make an amount
- largest that still fits, taken greedily
- make change with denominations
- prove optimality with an exchange argument
Looks similar, isn't
- Dynamic programming (1-D)
DP keeps every option open until the end. Greedy commits at once and cannot undo.
- Backtracking
Backtracking tries every choice and keeps the best. Greedy tries one and trusts it.
- Sort with a custom comparator
Most greedy solutions begin with a sort. The comparator is where the choice is written.
- Binary search on the answer
There the feasibility test is often greedy itself. The search only picks the value to test.
O(n log n) when the input has to be sorted first. The pass afterwards is a single loop, O(n).
On LeetCode
Problems that keep the most intervals with no overlap, or remove the fewest so the rest do not overlap. Sort by end time and keep each interval that starts at or after the last kept end.
Run the lesson's greedy and return how many intervals it skipped. Touching intervals do not overlap here, the same as in the lesson.
Shoot at the end of the first balloon by end time, and every balloon that starts at or before that point bursts too. Touching balloons share an arrow here, so a new arrow is needed only when a start is greater than the last end.
A chain is a set of pairs with no overlap, so sorting by the second number and taking greedily gives the longest one. The next pair must start strictly after the previous end.
Each event takes one day, so walk the days, push the ends of events that have started into a min-heap, drop the expired ones and attend the one that ends first.