145. Compile Packages with Dependencies in a Multi-Threaded Environment

Compile Packages with Dependencies in a Multi-Threaded Environment

You are given a dependency graph of packages to compile in a multithreaded environment.

The graph is provided as List<String> packages. Each string represents one row of the graph as a comma-separated list with no whitespace.

For a row "a,b,c", package a depends on packages b and c. This means b and c must be compiled before a.

For a row containing only one package name such as "x", package x has no dependencies.

A package can appear as a dependency even if it does not have its own row. Such a package is still part of the graph and is treated as a package with no dependencies unless it appears as the first package of some other row.

The number of worker threads is configurable. In one compilation round, you may compile at most threadCount packages that were already ready at the start of that round.

A package is ready if all of its dependencies have already been compiled in earlier rounds. Packages that become ready during a round can only be compiled in a later round.

In each round, if more than threadCount packages are ready, choose the lexicographically smaller package names first so that the result is deterministic.

Return the order in which packages are compiled across all rounds.

If the dependency graph contains a cycle, return an empty list.

Method Signature

List<String> compilePackages(List<String> packages, int threadCount)

packages is the dependency graph, where each row is a comma-separated string with no whitespace.
In a row "a,b,c", a is the package and b, c are its direct dependencies.
In a row "a", a has no direct dependencies.
threadCount is the maximum number of packages that can be compiled in one round.
Return a List<String> containing the packages in the order they are compiled.
Return an empty List<String> if no valid compilation order exists.

Constraints

1 ≤ packages.size() ≤ 10^4
1 ≤ threadCount ≤ 10^3
The total number of distinct packages in the graph is at most 10^5.
The total number of dependency relations is at most 2 * 10^5.
Each package name consists only of lowercase English letters, digits, underscore, or hyphen.
Each row contains no whitespace.
No row contains duplicate dependency names.
Each package appears as the first value in at most one row.

Examples

Example 1

Method call:

compilePackages(packages = List.of("app,core,ui", "core,util", "ui,util", "util"), threadCount = 2)

Output:

List.of("util", "core", "ui", "app")

Explanation:

Initially, only "util" is ready. After compiling "util", both "core" and "ui" become ready, and both can be compiled in the next round because threadCount = 2. They are listed as "core", "ui" because of lexicographical order. Finally, "app" becomes ready.

Example 2

Method call:

compilePackages(packages = List.of("backend,network,storage", "frontend,ui", "network", "storage", "ui"), threadCount = 2)

Output:

List.of("network", "storage", "backend", "ui", "frontend")

Explanation:

In the first round, "network", "storage", and "ui" are ready. Since only two packages can be compiled per round, choose the lexicographically smaller two: "network" and "storage". In the second round, "backend" and "ui" are ready, so compile them in lexicographical order: "backend" and then "ui". After that, "frontend" becomes ready.

Example 3

Method call:

compilePackages(packages = List.of("a,b", "b,c", "c,a"), threadCount = 3)

Output:

List.of()

Explanation:

There is a cycle a -> b -> c -> a, so no valid compilation order exists.

Example 4

Method call:

compilePackages(packages = List.of("app,core,ui", "core,util"), threadCount = 2)

Output:

List.of("ui", "util", "core", "app")

Explanation:

Package "ui" appears only as a dependency and has no own row, so it is treated as a package with no dependencies. Initially, "ui" and "util" are ready and are compiled in lexicographical order. Then "core" becomes ready, followed by "app".