Optimal Package Dispatch
You are tasked with optimizing package delivery operations for a logistics hub. You have a large number of packages, each with a specific destination and weight. To minimize operational costs and ensure efficient delivery, you need to dispatch these packages using the minimum number of drones. Drones have specific capacity and range limitations that must be adhered to.
Implement a function minDronesNeeded that calculates the minimum number of drones required to deliver all packages based on the given constraints.
Function Signature (TypeScript):
interface Package {
destination: number; // Distance from the hub (non-negative integer)
weight: number; // Weight of the package (positive integer)
}
function minDronesNeeded(
packages: Package[],
maxCapacity: number,
deliveryRange: number
): number
Input:
packages: An array of Package objects. Each Package has a destination (distance from hub, 0 to 10^9) and a weight (1 to 10^9). Destinations are not necessarily unique.maxCapacity: A positive integer representing the maximum total weight a single drone can carry (1 to 10^9).deliveryRange: A non-negative integer representing the maximum allowed difference between the furthest and closest destination for packages on a single drone (0 to 10^9). If a drone carries packages for destinations d_1, d_2, ..., d_k, it must hold that max(d_1, ..., d_k) - min(d_1, ..., d_k) <= deliveryRange.Output:
deliveryRange is 0, all packages on a single drone must have the exact same destination.Examples
Example 1
Input:
packages = [{"destination":10,"weight":5},{"destination":15,"weight":3},{"destination":20,"weight":8},{"destination":22,"weight":2},{"destination":25,"weight":4}], maxCapacity = 10, deliveryRange = 5
Output:
3
Note:
min_dest=10. max_dest_allowed=10 + 5 = 15.
Candidates within range [10,15] (excluding dispatched): (15,3). Heap: [(3, index of (15,3))].
Loads (15,3) (lightest). Total weight for this drone: 5+3=8 <= 10.
Drone 1 delivers (10,5), (15,3). Packages (10,5) and (15,3) are dispatched.min_dest=20. max_dest_allowed=20 + 5 = 25.
Candidates within range [20,25] (excluding dispatched): (22,2), (25,4). Heap: [(2, index of (22,2)), (4, index of (25,4))].
Loads (22,2) (lightest). Total weight: 8+2=10 <= 10.
Drone 2 delivers (20,8), (22,2). Packages (20,8) and (22,2) are dispatched.min_dest=25. max_dest_allowed=25 + 5 = 30.
No more undispatched packages in range.
Drone 3 delivers (25,4). Package (25,4) is dispatched.
Total drones: 3.Example 2
Input:
packages = [{"destination":10,"weight":10},{"destination":10,"weight":10},{"destination":11,"weight":1}], maxCapacity = 10, deliveryRange = 0
Output:
3
Note:
min_dest=10. max_dest_allowed=10.
No other packages with destination 10 can fit (weight 10+10 > 10).min_dest=10. max_dest_allowed=10.
No other packages with destination 10 can fit.min_dest=11. max_dest_allowed=11.
Total drones: 3.Example 3
Input:
packages = [{"destination":1,"weight":1},{"destination":2,"weight":1},{"destination":3,"weight":1},{"destination":4,"weight":1},{"destination":5,"weight":1}], maxCapacity = 3, deliveryRange = 10
Output:
2
Note:
min_dest=1. max_dest_allowed=1 + 10 = 11.
Candidates in range [1,11] (excluding dispatched): (2,1), (3,1), (4,1), (5,1). Heap: [(1,idx_2),(1,idx_3),(1,idx_4),(1,idx_5)]
Loads (2,1) (weight=2). Loads (3,1) (weight=3). Max capacity reached (3 <= 3).
Drone 1 delivers (1,1), (2,1), (3,1). Packages (1,1), (2,1), (3,1) are dispatched.min_dest=4. max_dest_allowed=4 + 10 = 14.
Candidates in range [4,14] (excluding dispatched): (5,1). Heap: [(1,idx_5)]
Loads (5,1) (weight=2).
Drone 2 delivers (4,1), (5,1). Packages (4,1), (5,1) are dispatched.
Total drones: 2.Constraints
0 <= packages.length <= 2000 (N). An empty array should return 0 drones.0 <= packages[i].destination <= 10^91 <= packages[i].weight <= 10^91 <= maxCapacity <= 10^90 <= deliveryRange <= 10^9maxCapacity, requiring multiple drones.packages.length = 0 or deliveryRange = 0 handled?Loading editor...