Saw, Then Paint
A workshop has one saw and one paint booth. Job i needs jobs[i][0] hours at the saw and after that jobs[i][1] hours in the booth.
Each machine works on one job at a time without a break in between. The jobs go through the saw in an order you choose, and through the booth in that same order. A sawn job may wait for the booth.
Both machines are free at time 0. Return the earliest time by which every job is painted.
Example 1
Job [1, 4] first: it is sawn at 1 and painted at 5. Job [3, 2] is sawn at 4, waits for the booth and is painted at 7. The other order ends at 9.
Example 2
Two hours at the saw, then two in the booth.
Example 3
The saw alone is busy until 10, and the last job still needs an hour of paint.
Constraints
1 <= len(jobs) <= 301 <= hours <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Greedy problems
- Seat the Pairs TogetherHard
- Two From Every IntervalHard
- Coins Handed BackBeginner
- Coins on the TableBeginner
- Fewest BanknotesBeginner
- Fewest JugsBeginner
- Greedy CoinsBeginner
- Least Total Waiting TimeBeginner