레시피 최소 완성 시간

문제

밀키트 회사의 주방에서 새 메뉴를 만듭니다. 레시피는 n개의 공정 으로 쪼개져 있고, 각 공정은 0부터 n-1까지 번호가 매겨져 있습니다.

• times[i]는 i번 공정을 끝내는 데 걸리는 시간(분)입니다.
• deps의 각 원소 [a, b]는 "a번 공정은 b번 공정이 완전히 끝난 뒤에 시작할 수 있다"는 뜻입니다.

주방에는 조리사가 넉넉해서, 선행 공정이 모두 끝난 공정은 몇 개든 동시에 시작할 수 있습니다. 시각 0에 선행 공정이 없는 공정들이 일제히 시작하고, 어떤 공정도 시작 가능해진 순간 곧바로 시작하며 한 번 시작하면 중간에 멈추지 않습니다.

모든 공정이 끝나는 최소 시각 을 반환하는 solution(times, deps) 함수를 작성하세요. 선행 관계에 모순(사이클)이 있어 끝낼 수 없는 공정이 하나라도 있으면 -1을 반환합니다.

예시

times=[3,2,4,1], deps=[[1,0],[2,0],[3,1],[3,2]] → 8
  0번은 시각 0에 시작해 3분에 끝남
  1번은 3분에 시작해 5분, 2번은 3분에 시작해 7분에 끝남 (동시 진행)
  3번은 1번·2번이 모두 끝난 7분에 시작해 8분에 끝남
 
times=[5,5,5], deps=[] → 5
  선행 관계가 없으므로 셋 다 시각 0에 동시 시작 → 5분
 
times=[2,3,4], deps=[[1,0],[2,1]] → 9
  일렬로만 진행 가능하므로 2+3+4 = 9분
 
times=[1,2,3], deps=[[0,1],[1,2],[2,0]] → -1
  0→1→2→0 순환이라 어떤 공정도 시작할 수 없음

제약 조건

• 1 ≤ n = times.length ≤ 100,000
• 1 ≤ times[i] ≤ 10,000
• 0 ≤ deps.length ≤ 200,000
• deps의 각 [a, b]에서 0 ≤ a, b ≤ n-1, a ≠ b이고 같은 쌍이 중복해서 주어지지 않습니다.
• 반환값은 정수입니다.

시간 복잡도 목표: O(n + deps.length)