Kitchen Ticket Rail
MediumOnline Assessment
Compute when each course of every table is ready to leave the kitchen, with a few cooks, a rush rail, and diners who take time between courses.
A kitchen has cooks cooks. Each ticket is [order, rush, gap, courses]: the table's order is fired at minute order; rush is 1 for a rush table and 0 otherwise; gap is the minutes diners spend eating between courses; and courses is a list of courses, each a list of dish cooking times in minutes.
A course is fired by putting all its dishes on the rail. A table's first course fires at its order minute. Each later course fires gap minutes after the previous course's pickup, the minute its last dish finishes. A cook who is free takes the best waiting dish on the rail immediately and works on it, without interruption, for its cooking time. The best dish is chosen by: rush tickets first; then the earlier fire minute; then the lower ticket number (position in the list); then the earlier dish in its course.
When several things happen in the same minute, the order is: dishes finish (freeing cooks and possibly completing courses, which may schedule a zero-gap fire for that same minute), then courses fire, then free cooks take dishes from the rail.
Input: cooks, a positive integer; tickets, a list of tickets as above (every ticket has at least one course and every course at least one dish; tickets are not sorted by order).
Output: for each ticket, in the given order, the list of its courses' pickup minutes.
Example 1
- Input:
- [2,[[0,0,5,[[4,6],[3]]],[0,0,0,[[5]]]]]
- Output:
- [[6,14],[9]]
- Explanation
- Two cooks. At minute 0 table 0's two dishes (4 and 6 minutes) and table 1's dish (5) are on the rail. The cooks take table 0's dishes, leaving table 1 waiting until the 4-minute dish is done at minute 4; its dish finishes at 9. Table 0's first course is picked up at 6 (its last dish), the diners eat for 5 minutes, and the second course fires at 11 and finishes at 14.
Example 2
- Input:
- [1,[[0,0,2,[[5],[5]]],[1,1,0,[[4]]],[2,0,0,[[3]]]]]
- Output:
- [[5,17],[9],[12]]
- Explanation
- One cook. Table 0's first dish runs from 0 to 5. Table 1 (a rush table) fires at 1 and table 2 at 2. When the cook frees at 5, table 0 is picked up and its second course will fire at 7. The rush table goes first (5 to 9); at 9 table 2 (fired at 2) beats table 0's second course (fired at 7), so it runs 9 to 12, and table 0's second course runs 12 to 17.
Example 3
- Input:
- [2,[[0,0,0,[[3,3],[3]]],[0,0,0,[[2],[2,2]]]]]
- Output:
- [[3,6],[5,8]]
- Explanation
- Two cooks, all gaps zero. Table 0's two 3-minute dishes take both cooks at minute 0, so table 1's first dish waits until minute 3. At minute 3 table 0's first course is picked up and its second course fires at once; table 1's dish (fired at 0) goes first, then table 0's second course, giving pickups 5 and 6. Table 1's second course (two 2-minute dishes) fires at 5; one dish starts at 5 and the other when the cook frees at 6, so the course is picked up at 8.
Constraints
- 1 ≤ cooks ≤ 6; 1 ≤ tickets.length ≤ 25
- 0 ≤ order ≤ 300; rush is 0 or 1; 0 ≤ gap ≤ 40
- 1 ≤ courses.length ≤ 4; 1 ≤ dishes per course ≤ 5; 1 ≤ dish time ≤ 20