Frontend School

Minimum Parallel Teams for Project Completion

DSA
hard

Minimum Parallel Teams for Project Completion

Hard
Graph
Topological Sort
Binary Search
Priority Queue
Scheduling

Overview

In large-scale software development, managing complex projects with numerous interdependent tasks is crucial. Efficient resource allocation, specifically the number of parallel teams, directly impacts project timelines and costs. This problem simulates a scenario where you need to determine the minimum number of parallel teams required to complete a project within a strict time limit, respecting all task dependencies.

What you need to do / Task

Implement a function minTeamsForProject that takes the project's details and a time limit, and returns the minimum number of parallel teams needed to complete all tasks within that limit. If it's impossible to complete the project within the given timeLimit even with all tasks running in parallel (i.e., numTasks teams), your function should return -1.

Your solution must:

  1. Model Dependencies: Correctly represent task prerequisites as a directed acyclic graph (DAG).
  2. Schedule Tasks: Implement a scheduling mechanism that assigns tasks to available teams, respecting prerequisites and team availability.
  3. Optimize Teams: Use an efficient approach to find the minimum number of teams required.
  4. Adhere to Time Limit: Ensure the total project completion time does not exceed timeLimit.

Input & output

function minTeamsForProject(numTasks: number, taskDurations: number[], prerequisites: number[][], timeLimit: number): number
  • numTasks: An integer, the total number of tasks in the project. Tasks are indexed from 0 to numTasks - 1.
  • taskDurations: An array of integers, where taskDurations[i] is the time (in some arbitrary units) required to complete task i.
  • prerequisites: An array of [pre, post] pairs, where pre is a task that must be completed before post can begin. Each pre and post are task indices.
  • timeLimit: An integer, the maximum allowed total time for the entire project to be completed.

Returns: An integer representing the minimum number of parallel teams required. Return -1 if the project cannot be completed within timeLimit under any number of teams (up to numTasks).

Clarifications

  • Tasks are identified by their 0-based index.
  • There will be no circular dependencies in the prerequisites (the graph is a DAG).
  • Each team can work on exactly one task at a time. Once a task is assigned to a team, that team is busy for the duration of the task.
  • If numTasks is 0, the function should return 0 teams.
  • Task durations can be 0. A task with 0 duration still takes up a team for an infinitesimal amount of time but finishes immediately.

Examples

1

Example 1

Input:

numTasks = 3, taskDurations = [10, 5, 8], prerequisites = [[0, 2], [1, 2]], timeLimit = 20

Output:

2

Note:

Tasks: T0 (10), T1 (5), T2 (8). Dependencies: T0 -> T2, T1 -> T2.

  • With 1 team: T0 (0-10), T1 (10-15), T2 (15-23). Total time: 23, which exceeds 20. Impossible.
  • With 2 teams:
    • Time 0: Team 1 takes T0 (finishes at 10). Team 2 takes T1 (finishes at 5).
    • Time 5: Team 2 is free. T0 is still running. No tasks are ready for Team 2.
    • Time 10: Team 1 is free. T0 is completed. Both T0 and T1 are done, so T2 can start. Team 1 takes T2 (finishes at 10+8=18). Team 2 remains free.
    • All tasks finished by time 18. Since 18 <= 20, it's possible. Minimum teams is 2.
2

Example 2

Input:

numTasks = 4, taskDurations = [3, 2, 4, 1], prerequisites = [[0, 2], [1, 2], [2, 3]], timeLimit = 10

Output:

1

Note:

Tasks: T0 (3), T1 (2), T2 (4), T3 (1). Dependencies: T0 -> T2, T1 -> T2, T2 -> T3.

  • With 1 team:
    • Time 0: T0 starts (finishes 3).
    • Time 3: T1 starts (finishes 5).
    • Time 5: T2 starts (needs T0, T1; finishes 9).
    • Time 9: T3 starts (needs T2; finishes 10).
    • All tasks finished by time 10. Since 10 <= 10, it's possible. Minimum teams is 1.
3

Example 3

Input:

numTasks = 2, taskDurations = [100, 1], prerequisites = [[0, 1]], timeLimit = 50

Output:

-1

Note:

Tasks: T0 (100), T1 (1). Dependency: T0 -> T1.

  • T0 must complete before T1 starts. Even with infinite teams, T0 takes 100 units of time. T1 then takes 1 unit. The total project time will be at least 100 + 1 = 101.
  • Since 101 > 50, it's impossible to complete within the time limit.

Constraints

Constraints & assumptions

  • 0 <= numTasks <= 10^5
  • 0 <= taskDurations[i] <= 1000
  • 0 <= prerequisites.length <= 2 * 10^5
  • 0 <= timeLimit <= 10^9
  • prerequisites[j] contains exactly two elements: [pre, post]
  • 0 <= pre, post < numTasks
  • The graph formed by tasks and prerequisites is guaranteed to be a Directed Acyclic Graph (DAG).

What interviewers evaluate

  • Correctness: The solution must correctly determine the minimum number of teams, handling all dependencies, resource constraints, and edge cases (e.g., numTasks = 0, timeLimit = 0, tasks with 0 duration).
  • Efficiency: The solution should have optimal time and space complexity, suitable for numTasks up to 10^5 and prerequisites up to 2 * 10^5.
  • Algorithm Design: Demonstrates a clear understanding and application of graph algorithms (topological sort) combined with an optimization strategy (binary search) and efficient data structures (priority queues).
  • Code Quality: Well-structured, readable, and maintainable code with appropriate data structure choices and comments where necessary.

Loading editor...