Katkat
Back

Compute total time to finish all courses

SnowflakeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model task dependencies using a directed graph and calculate the earliest completion time for all tasks, effectively identifying the critical path in a project schedule.

Problem Statement

You are given a list of courses that need to be completed. Each course has a specific duration (in hours) and a list of prerequisite courses that must be finished before starting it. A course can be started as soon as all its prerequisites are completed. You can work on any number of courses simultaneously, provided their prerequisites are met.

Calculate the total time required to finish all courses. If it is impossible to complete all courses due to a circular dependency, return -1.

Function Signature

def get_total_completion_time(durations: List[int], prerequisites: List[List[int]]) -> int:
  • durations: A list where durations[i] is the time in hours to complete course i.
  • prerequisites: A list of pairs [a, b] where course b must be finished before course a can start.

Examples

Example 1:

  • durations = [3, 2, 5]
  • prerequisites = [[2, 0], [2, 1]]
  • Output: 8
  • Explanation: Course 0 (3h) and 1 (2h) can run in parallel. Course 2 starts after both are done. Total = max(3, 2) + 5 = 8.

Example 2:

  • durations = [2, 2]
  • prerequisites = [[0, 1], [1, 0]]
  • Output: -1
  • Explanation: Circular dependency; impossible to finish.

Constraints

  • Number of courses n is between 1 and 10^4.
  • 0 = 0.

Hints

Hint 1

Represent the courses as nodes in a Directed Acyclic Graph (DAG) and the prerequisites as edges.

Hint 2

Think of this as finding the 'longest path' in the graph where the weight of each path is the sum of the durations of the courses along that path.

Hint 3

Consider using Kahn's algorithm (topological sort) to compute the earliest start time for each course as you traverse the nodes.

Follow-up questions

  • What is the time and space complexity of your solution in terms of nodes (V) and edges (E)?
  • How would you modify the algorithm if some courses could be completed only after a specific machine or resource becomes available?
  • If you were asked to find the 'critical path' (the specific sequence of courses that dictates the total duration), how would you reconstruct it?