Frontend School

Optimal Package Dispatch

DSA
hard

Optimal Package Dispatch

Hard
Greedy
Priority Queue
Sorting

Overview

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.

What you need to do / Task

Implement a function minDronesNeeded that calculates the minimum number of drones required to deliver all packages based on the given constraints.

Deliverables:

  1. Sort packages: Packages must be processed strategically. Determine an optimal sorting order.
  2. Greedy Dispatch: For each drone dispatched, apply a greedy strategy to load as many eligible packages as possible to minimize the total number of drones.
  3. Constraint Adherence: Ensure that each drone adheres to both its maximum weight capacity and the destination range constraint for all packages it carries.

Input & output

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:

  • A single integer representing the minimum number of drones required to dispatch all packages.

Clarifications

  • All packages must be delivered.
  • A drone can carry multiple packages as long as the constraints are met.
  • If deliveryRange is 0, all packages on a single drone must have the exact same destination.
  • Packages are not necessarily sorted in the input array.

Examples

1

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:

  1. Sort packages by destination: [(10,5), (15,3), (20,8), (22,2), (25,4)]
  2. Drone 1: Picks (10,5). 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.
  3. Drone 2: Next undispatched is (20,8). Picks (20,8). 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.
  4. Drone 3: Next undispatched is (25,4). Picks (25,4). 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.
2

Example 2

Input:

packages = [{"destination":10,"weight":10},{"destination":10,"weight":10},{"destination":11,"weight":1}], maxCapacity = 10, deliveryRange = 0

Output:

3

Note:

  1. Sort packages: [(10,10), (10,10), (11,1)]
  2. Drone 1: Picks (10,10) (first one). min_dest=10. max_dest_allowed=10. No other packages with destination 10 can fit (weight 10+10 > 10).
  3. Drone 2: Picks (10,10) (second one). min_dest=10. max_dest_allowed=10. No other packages with destination 10 can fit.
  4. Drone 3: Picks (11,1). min_dest=11. max_dest_allowed=11. Total drones: 3.
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:

  1. Sort packages: [(1,1), (2,1), (3,1), (4,1), (5,1)]
  2. Drone 1: Picks (1,1). 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.
  3. Drone 2: Next undispatched is (4,1). Picks (4,1). 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

Constraints & assumptions

  • 0 <= packages.length <= 2000 (N). An empty array should return 0 drones.
  • 0 <= packages[i].destination <= 10^9
  • 1 <= packages[i].weight <= 10^9
  • 1 <= maxCapacity <= 10^9
  • 0 <= deliveryRange <= 10^9
  • The total weight of all packages might exceed maxCapacity, requiring multiple drones.

Out of scope

  • Calculating optimal drone paths or fuel consumption beyond the problem's scope.
  • Handling invalid input (e.g., negative weights, non-integer values).

What interviewers evaluate

  • Correctness of Greedy Strategy: Does the chosen greedy approach consistently lead to the optimal solution?
  • Algorithmic Efficiency: Is the solution optimized for the given constraints (e.g., O(N^2 log N) or better)?
  • Edge Case Handling: How are scenarios like packages.length = 0 or deliveryRange = 0 handled?
  • Code Structure and Readability: Clarity, modularity, and adherence to best practices.

Loading editor...