2dbi
Home/Atlassian/Minimum Sprints to Complete All Tasks Given Dependencies
AAtlassian·DSAL4Coding Assessment

Minimum Sprints to Complete All Tasks Given Dependencies

Problem

You have n tasks (0 to n-1) and a list of dependencies [a, b] meaning task b must complete before task a. Tasks with no pending dependencies can run in parallel within the same sprint. Find the minimum number of sprints to complete all tasks.

Example

n = 6
dependencies = [[2,0],[2,1],[3,1],[4,3],[5,2],[5,3]]
Output: 4

Approach

Topological BFS (Kahn's algorithm). The answer is the length of the longest dependency chain.

Constraints

  • 1 ≤ n ≤ 10^4
  • Acyclic graph guaranteed (valid sprint plan exists)

Atlassian follow-up

What if a task can be split across sprints? What if certain tasks have a fixed sprint they must start in?

added 6 days ago
LeadersAccount