Minimum Time to Finish Dependent Cake-Making Steps When Steps Can Run in Parallel

A bakery breaks the job of making a cake into `n` steps labeled `0` to `n - 1`, such as preheating the oven, mixing the batter, baking, making the frosting and frosting the cake. Step `i` takes `durations[i]` minutes. Some steps need others to be done first: the pair `[u, v]` in `dependencies` means step `u` must be completely finished before step `v` can start. Together the steps and dependencies form a directed graph with no cycles. The kitchen has enough people and equipment for any number of steps to be in progress at the same time. Return the minimum number of minutes after which every step of the cake is finished. ### Function Signature ```python def min_finish_time(n: int, dependencies: list[list[int]], durations: list[int]) -> int: ``` `n` is the number of steps, each `dependencies[j] = [u, v]` means step `u` must finish before step `v` starts, and `durations[i]` is the length of step `i` in minutes. ### Rules - Work starts at minute `0`. A step with no dependencies may start at minute `0`. - A step may start at, or any time after, the moment the last of its prerequisite steps finishes, never earlier. Once started, step `i` runs without pausing and finishes exactly `durations[i]` minutes later. - Any number of steps may run at the same time; nothing other than `dependencies` limits when a step can start. - Step labels say nothing about order: a step may depend on a step with a larger label. - Return the smallest possible time, in whole minutes, at which all `n` steps have finished. ### Constraints - `1 <= n <= 5 * 10^4` - `len(durations) == n` and `1 <= durations[i] <= 10^4` - `0 <= len(dependencies) <= 5 * 10^4` - Each pair is `[u, v]` with `0 <= u, v <= n - 1` and `u != v`. - No pair appears twice. - The dependencies contain no cycle, so every step can eventually run. - The answer is at most `5 * 10^8`, which fits in a signed 32-bit integer. ### Examples **Example 1** ```text Input: n = 7, dependencies = [[1, 3], [2, 3], [0, 4], [3, 4], [4, 6], [5, 6]], durations = [10, 4, 6, 3, 30, 12, 5] Output: 45 ``` The steps are: 0 preheat the oven, 1 mix the dry ingredients, 2 whisk the wet ingredients, 3 combine them into batter, 4 bake, 5 make the frosting, 6 frost the cake. Steps 0, 1, 2 and 5 start at minute 0. The batter can be combined once both mixes are done at minute 6 and is ready at minute 9, but baking also needs the oven, which is hot at minute 10, so baking runs from minute 10 to minute 40. The frosting has been ready since minute 12, so frosting the cake runs from minute 40 to minute 45. **Example 2** ```text Input: n = 3, dependencies = [], durations = [7, 2, 5] Output: 7 ``` No step depends on another, so all three run at the same time and everything is finished when the 7-minute step ends. **Example 3** ```text Input: n = 4, dependencies = [[3, 0], [2, 0], [0, 1]], durations = [2, 1, 5, 4] Output: 8 ``` Steps 2 and 3 start at minute 0 and finish at minutes 5 and 4. Step 0 needs both, so it runs from minute 5 to minute 7, and step 1 then runs from minute 7 to minute 8. Running the four steps one after another would take 12 minutes.