Festival Screening Flex Windows
Start-time slack per node in a minimum-duration dependency graph schedule
A film festival has n screenings, numbered from 0 to n - 1. Screening i runs for durations[i] minutes.
Each pair [a, b] in dependencies means screening b cannot start until screening a has finished. Every screening must start at or after time zero. The festival has enough rooms to run any number of screenings simultaneously, and there are no restrictions other than the dependencies.
Let T be the smallest possible time by which all screenings can finish. Consider all schedules that finish by T. For each screening i, let:
earliest[i]be its earliest possible start time among these schedules;latest[i]be its latest possible start time among these schedules.
Return an array whose element at index i is latest[i] - earliest[i]. This is the screening's flex window: how much its start can vary while preserving the festival's fastest possible completion time. Each screening's window is considered independently; the latest starts need not be chosen independently of the other screenings' start times.
If the dependencies contain a directed cycle, no schedule is possible. In that case, return [-1].
Examples
Example 1
Input: n = 4, durations = [4,3,2,5], dependencies = [[0,2],[1,2],[2,3]] Output: [0,1,0,0]
Screenings 0 and 1 can run concurrently, but screening 2 must wait for both, and screening 3 must wait for screening 2. The branch through screening 0 determines the festival's completion time, while screening 1 has some scheduling flexibility.
Example 2
Input: n = 3, durations = [2,7,3], dependencies = [] Output: [5,0,4]
There are no dependencies, so all screenings can start immediately. Each shorter screening can also start later, provided it still finishes by the completion time required by the longest screening.
Example 3
Input: n = 2, durations = [3,4], dependencies = [[0,1],[1,0]] Output: [-1]
The dependencies require each of the two screenings to finish before the other starts, so no schedule is possible.
Constraints
- 1 <= n <= 2000
- durations.length == n
- 1 <= durations[i] <= 1000000000
- 0 <= dependencies.length <= 3000
- Each dependency is a pair [a, b] with 0 <= a, b < n and a != b.
- Dependencies contain no duplicate ordered pairs.
The intended solution uses O(n + dependencies.length) time and space. Completion times may exceed 32-bit integer limits, but remain exactly representable by JavaScript numbers under these constraints.
Hints
Show hint 1Hint 1
A topological traversal can both detect an impossible dependency cycle and compute the earliest start of each screening.
Show hint 2Hint 2
Traverse the topological order backward to find the longest remaining duration beginning at each screening. How does this constrain its latest start?
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return one schedule that starts every screening as late as possible while still achieving the minimum completion time?
- How would the answer change if dependencies also specified a nonnegative waiting time between the two screenings?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem