Find bottleneck dependencies in a parallel build

You are given n build targets numbered 0 to n - 1 and a list of directed edges edges. An edge [u, v] means target v cannot start building until target u has finished. The graph has no cycles.

The build runs on a clock with unlimited parallel builders:

• Every target takes exactly one time step to build.
• A target starts in the first time step after all of its prerequisites have finished. Targets with no prerequisites build in step 1.
• Any number of targets can build in the same step.

A target is a bottleneck if it is the only target building during its time step.

Implement:

def find_bottlenecks(n: int, edges: list[tuple[int, int]]) -> list[int]:
    ...

Return the bottleneck targets in the order they are built. If the input contains a cycle, raise an error.

Constraints

• 0 <= n <= 10^5
• 0 <= len(edges) <= 2 * 10^5
• 0 <= u, v < n, u != v

Example 1

n = 4
edges = [[0, 1], [0, 2], [1, 3], [2, 3]]

Step 1 builds {0}, step 2 builds {1, 2}, step 3 builds {3}. Output: [0, 3].

Example 2

n = 5
edges = [[0, 1], [2, 3], [3, 4]]

Step 1 builds {0, 2}, step 2 builds {1, 3}, step 3 builds {4}. Output: [4].

Be ready to extend your solution to targets with different build durations.

Reconstructed from the reported question; details may differ from what interviewers ask.