PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
This problem can be solved using dynamic programming. We assign dishes to the ovens, one at a time, and in the order they must be completed, while memoizing:
memo[d1][d2][t] = number of minutes required to finish cooking all dishes, where
- first chef’s first d1 dishes have been assigned to an oven
- second chef’s first d2 dishes have been assigned to an oven
- one of the ovens has just finished cooking all of the dishes assigned to it, and the other will finish cooking all of the dishes assigned to it in t minutes
From each state, the next dish we assign can be from either chef, and can go in either oven. In order to satisfy the order constraint, when we assign a dish to an oven we require it to finish cooking at the same time or after the last dish assigned to the other oven.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.