Problem Breakdown
Kitchen Orders
Published ·
hard
A kitchen has to cook an order made of several dishes. Each dish follows a recipe, which is a fixed sequence of station steps, and you assign every step to one of three chefs. The goal is to finish the whole order as fast as possible. Picking the fastest chef for each step is a good start, but the order you schedule those steps in matters too. On our three-dish example, changing that order saves 30 seconds.
The setup
An order holds a list of dishes. Each dish has a recipe, and a recipe is an ordered list of station steps with a base time in seconds. There are three stations.
| Recipe | Steps |
|---|---|
| Burger | PREP 30 → GRILL 90 |
| Salad | PREP 30 → CHOP 60 |
| Pasta | PREP 30 → CHOP 60 → GRILL 90 |
There are three chefs, and each one runs some stations faster than others. A chef's actual time on a step is the step's base time multiplied by that chef's factor for the station.
| Chef | PREP | CHOP | GRILL |
|---|---|---|---|
| Alice | 1.5 | 1.5 | 0.5 |
| Bob | 1.5 | 0.5 | 1.5 |
| Carol | 0.5 | 1.5 | 1.5 |
Every station has exactly one specialist who runs it at half time, and the other two run it at one-and-a-half times. So the fast times are PREP 15 (Carol), CHOP 30 (Bob), and GRILL 45 (Alice), and the slow times are three times as long. Three rules keep a schedule honest. The steps inside a dish run in recipe order, a chef does one step at a time, and a station holds one chef at a time. The makespan is the moment the last step finishes, and that's the number we minimize.
The order [Burger, Salad, Pasta] is small enough to reason about by hand. Its optimum is 105 seconds, while the first two solutions both take 135. The practice tests check each returned schedule against a makespan target. That target isn't passed to your scheduler.
We're implementing Kitchen.schedule(order), which returns a Schedule containing one ScheduleEntry per dish step. Each entry records the dish, chef, station, and start and end times. This method builds a plan without running any of the steps. Entries created one after another can describe work that overlaps in time.
Solution 1, the greedy pass
The natural first attempt walks the dishes in the order they arrive. For each step of each dish, you hand the step to whichever chef can finish it earliest, and you start it at the earliest moment that's actually legal. That earliest legal start is the latest of three times. The dish's previous step has to be done, the chef has to be free, and the station has to be free.
Complexity
Where it breaks
Schedule Pasta before Salad
Solution 2, dispatch the best ready step
Complexity
Where it breaks
Solution 3, search the orderings
Complexity
Where it wins
Benchmarks
Takeaways
Purchase Premium to Keep Reading
Unlock this article and so much more with Hello Interview Premium