Total Duration of Related Jobs
Problem statement
Jobs have IDs 0 through durations.length - 1. Job i takes durations[i] time units. A pair [parent, child] means that child is a child job of parent.
Starting with startJob, find that job and every job reachable by following zero or more child edges. Return the sum of their durations. Count a shared descendant only once, even when several paths reach it. Ignore unrelated jobs.
Scheduling rule for this exercise: the selected jobs run once each on a single worker. The returned sum is their total work and elapsed execution time under this rule. It is not an unlimited-parallel-worker completion time. A valid dependency order exists because the graph is acyclic; you do not need to return that order.
Function
relatedJobDuration(durations: long[], childPairs: int[][], startJob: int) → longExamples
Example 1
durations = [3,5,7,11]childPairs = [[0,1],[0,2],[1,3],[2,3]]startJob = 0return = 26The selected jobs are 0,1,2,3. Job 3 is reachable through both 1 and 2, but runs once. The sum is 3 + 5 + 7 + 11 = 26.
Example 2
durations = [8,2,4,100]childPairs = [[0,1],[1,2]]startJob = 1return = 6Starting at job 1 selects 1 and its child 2. Job 0 is an ancestor, and job 3 is unrelated; neither is selected. Return 2 + 4 = 6.
Example 3
durations = [0]childPairs = []startJob = 0return = 0The starting job is still selected. Its duration is zero, so the total is zero.
Constraints
1 <= durations.length <= 2000 <= durations[i] <= 10000000000 <= childPairs.length <= 1000- Every row of
childPairshas exactly two integers in[0, durations.length - 1]. 0 <= startJob < durations.length- The directed child graph is acyclic, has no self edges, and has no repeated edges.