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