Katkat
Back

Compute Minimum Task Completion Time

NetflixSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model task dependencies as a Directed Acyclic Graph (DAG) and compute the longest path in that graph to determine the earliest completion time.

Problem Statement

You are given a list of tasks that need to be completed. Each task has a unique ID from 0 to n-1, a duration, and a list of prerequisite tasks that must be finished before it can start. You can perform any number of independent tasks simultaneously, provided their prerequisites are met. Your goal is to find the minimum total time required to complete all tasks.

Function Signature

def min_completion_time(n: int, durations: List[int], prerequisites: List[List[int]]) -> int:

Input

  • n: The number of tasks.
  • durations: A list where durations[i] is the time taken to complete task i.
  • prerequisites: A list of pairs [u, v] where task u must be finished before task v can start.

Constraints

  • 1 <= n <= 10,000
  • 0 <= len(prerequisites) <= 100,000
  • If a cycle exists, return -1.

Examples

Example 1:

  • n = 3, durations = [3, 2, 5]
  • prerequisites = [[0, 2], [1, 2]]
  • Output: 8
  • Explanation: Task 0 (3) and Task 1 (2) can run in parallel. Task 2 depends on both, so it starts after the max of (3, 2) and finishes at 3+5=8.

Example 2:

  • n = 2, durations = [1, 1]
  • prerequisites = [[0, 1], [1, 0]]
  • Output: -1
  • Explanation: Cyclic dependency exists.

Edge Cases

  • Disconnected components in the graph.
  • Tasks with no prerequisites.
  • Tasks with no dependencies.

Hints

Hint 1

Represent the dependencies as an adjacency list and compute the in-degree of each node.

Hint 2

Use Kahn's algorithm (topological sort) to process nodes, maintaining a 'completion_time' array where `time[v] = max(time[v], time[u] + duration[v])` for all dependencies `u` of `v`.

Hint 3

If the number of processed nodes after topological sort is less than `n`, a cycle must exist.

Follow-up questions

  • How would you identify which tasks are on the 'critical path' (tasks that, if delayed, delay the entire project)?
  • How would the solution change if you had a limited number of worker threads (e.g., only 2 workers can run tasks at once)?
  • What is the time and space complexity of your approach in terms of tasks and dependencies?