Earliest Dependency Schedule
Headlands Technologies● MediumFULLTIMEOAProblem statement
There are N jobs with indices from 0 through N - 1. Job i takes durations[i] units of time. Each dependency [before, after] means that job after can start only when job before has finished.
The dependency graph is acyclic. All jobs are available at time 0, and there are unlimited workers, so independent jobs may run simultaneously. Start every job as early as its dependencies allow.
Return a flattened array of start and finish times in job-index order: [start[0], finish[0], start[1], finish[1], ...]. A job with no prerequisites starts at 0. Any other job starts at the latest finish time among all its direct prerequisites; its finish time is its start time plus its duration.
If there are no jobs, return an empty array. The input is valid; no error output for cycles or invalid indices is required.
Function
earliestSchedule(durations: int[], dependencies: int[][]) → long[]Examples
Example 1
durations = [3,2,4,1]dependencies = [[0,2],[1,2],[2,3]]return = [0,3,0,2,3,7,7,8]Jobs 0 and 1 start at time 0. Job 2 waits until both finish, at time 3; job 3 starts when job 2 finishes at time 7.
Example 2
durations = []dependencies = []return = []There are no jobs, so the schedule has no start or finish values.
Example 3
durations = [5,7,11]dependencies = [[2,1],[1,0]]return = [18,23,11,18,0,11]Job 2 runs first from time 0 to 11, followed by job 1 and then job 0. Return pairs in job-index order, rather than execution order.
Constraints
0 <= N <= 10^5.0 <= dependencies.length <= 2 * 10^5.1 <= durations[i] <= 10^9.- Each dependency has exactly two valid job indices, no self-edge or duplicate edge occurs, and the directed graph is acyclic.
- When
N = 0, the dependency list is empty. - Return times as signed 64-bit integers. A path duration is at most
10^14.