1
/**
2
 * @param {number} n
3
 * @param {number[][]} relations
4
 * @param {number[]} time
5
 * @return {number}
6
 */
7
var minimumTime = function (n, relations, time) {
8
  /*
9
    Approach: We can create reverse edges for relation.
10
    Then longest path(by weightage of time for each node) from the node will be the minimum time to finish that course(node)
11
    Now we can use simple DFS to find the longest path for each node.
12
    The node containing the longest path will be course to finish the last.We can also use memo to save the longest path from node, so when we reach to this node, we need not to calculate the longest path again. 
13
    */
14
  let edges = {};
15
  for (let i = 0; i < relations.length; i++) {
16
    if (edges[relations[i][1]] === undefined) {
17
      edges[relations[i][1]] = [];
18
    }
19
    edges[relations[i][1]].push(relations[i][0]);
20
  }
21

22
  let max = 0,
23
    timeRequired,
24
    memo = {};
25
  for (let i = 1; i <= n; i++) {
26
    timeRequired = longestPath(i);
27
    max = Math.max(max, timeRequired);
28
  }
29
  return max;
30
  function longestPath(node) {
31
    if (memo[node] !== undefined) {
32
      return memo[node];
33
    }
34
    let len,
35
      max = 0;
36
    if (edges[node] !== undefined) {
37
      for (let i = 0; i < edges[node].length; i++) {
38
        len = longestPath(edges[node][i]);
39
        max = Math.max(max, len);
40
      }
41
    }
42
    memo[node] = time[node - 1] + max; //use memo to save the longest path from node, so when we reach to this node, we need not to calculate the longest path again
43
    return memo[node];
44
  }
45
};