Warehouse Package Scheduling
Flipkart's warehouses handle millions of packages daily. Efficient processing and loading are crucial for timely deliveries and customer satisfaction. Some packages have interdependencies – for instance, a fragile item might need special packaging before it can be combined with other items on a pallet, or certain documents must be processed before their associated physical packages can be moved. This problem focuses on determining a valid sequence for processing packages based on these dependencies to ensure smooth and error-free operations.
Implement a function that takes the total number of packages and a list of their direct dependencies, then returns a valid processing order.
numPackages (an integer representing the total count of packages, labeled from 0 to numPackages - 1) and dependencies (an array of [prerequisite, dependent] pairs).[p, d] signifies that package p must be fully processed before package d can begin processing.numPackages. Each package must appear exactly once in the returned order.[].numPackages: An integer, N, representing the total number of unique packages, identified by zero-based indices from 0 to N-1.dependencies: An array of number[] where each inner array [p, d] denotes a direct dependency: package p must be processed before package d.number[] representing a valid processing order of all packages. If no such order exists due to circular dependencies, return an empty array [].numPackages - 1).A must precede B, and B must precede C, you will be given [A, B] and [B, C], but not necessarily [A, C] (though A indirectly precedes C).dependencies is empty, any order is valid. A simple natural order [0, 1, ..., numPackages-1] is acceptable.numPackages is 0, an empty array [] should be returned.Examples
Example 1
Input:
numPackages = 4, dependencies = [[1,0],[2,0],[3,1],[3,2]]
Output:
[3,1,2,0]
Note:
Package 3 must be processed before 1 and 2. Packages 1 and 2 must be processed before 0. A valid processing order is 3, then 1, then 2, then 0. Another valid order would be [3,2,1,0].
Example 2
Input:
numPackages = 3, dependencies = [[0,1],[1,2],[2,0]]
Output:
[]
Note:
There is a circular dependency (0 -> 1 -> 2 -> 0), which means no valid processing order can be achieved for all packages. Thus, an empty array is returned.
Example 3
Input:
numPackages = 3, dependencies = []
Output:
[0,1,2]
Note:
With no dependencies, any order is valid. The simplest is the natural order of package indices.
Constraints
1 <= numPackages <= 10^50 <= dependencies.length <= min(numPackages * (numPackages - 1) / 2, 10^5)0 <= prerequisite, dependent < numPackages for all [prerequisite, dependent] pairs.prerequisite and dependent values in dependencies are valid package indices within the numPackages range.numPackages, prerequisite or dependent outside of [0, numPackages-1] range).Loading editor...