Code RoomMinimum path cover
HardPrep Room Coding #1447

Minimum path cover

CodingAlgorithms & data structuresSenior–Staff~35 min

You have n tasks (nodes 0..n-1) and a list of directed precedence edges forming a DAG; edge [u, v] means task u can be immediately followed by task v on the same worker. A worker processes a chain of tasks where each consumes the next via such an edge, and every task must be done by exactly one worker. Return the minimum number of workers needed so that each task is covered exactly once (the minimum number of vertex-disjoint paths that cover all nodes). Constraints: 1 <= n <= 60; the graph is a DAG with no self loops.

Implement
min_path_cover(n: int, edges: list[list[int]]) → int
Examples
in[4,[[0,1],[1,2],[0,3]]]out2
What a strong answer looks like

State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.

0:00 of about 35 min
InputExpectedGot
[4,[[0,1],[1,2],[0,3]]]2not run yetsample