Frontend School

Minimize Maximum Load per Delivery Agent

DSA
medium

Minimize Maximum Load per Delivery Agent

Medium
Binary Search
Arrays
Greedy

Overview

At Delhivery, efficient package distribution is critical for timely deliveries and optimal resource utilization. Mismanaging agent workload can lead to delays, agent fatigue, and increased operational costs. This problem challenges you to find the most balanced way to distribute packages among available agents, minimizing the maximum load any single agent has to carry.

What you need to do / Task

Your task is to implement a function that determines the minimum possible value for the maximum total weight carried by any single delivery agent. You are given a list of package weights and the total number of agents available.

  • Each package must be assigned to exactly one agent.
  • Agents can carry multiple packages.
  • The goal is to minimize the largest sum of package weights assigned to any one agent.

Input & output

Function Signature: function minimizeMaxLoad(packageWeights: number[], numAgents: number): number

  • packageWeights: An array of integers where packageWeights[i] represents the weight of the i-th package.
  • numAgents: An integer representing the total number of delivery agents available.

Returns: An integer representing the minimum possible value for the maximum total weight carried by any single agent.

Clarifications

  • Empty packageWeights? The array packageWeights will always contain at least one package.
  • numAgents vs packageWeights.length? numAgents will always be between 1 and packageWeights.length (inclusive). If numAgents equals packageWeights.length, each agent carries one package, and the answer is the maximum individual package weight. If numAgents is 1, one agent carries all packages, and the answer is the sum of all package weights.

Examples

1

Example 1

Input:

packageWeights = [10, 20, 30, 40, 50], numAgents = 2

Output:

90

Note:

With a maximum load of 90: Agent 1 can take [10, 20, 30] (total 60) and Agent 2 takes [40, 50] (total 90). No agent exceeds 90. If the maximum load was 89, it would require 3 agents.

2

Example 2

Input:

packageWeights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], numAgents = 5

Output:

15

Note:

With a maximum load of 15: Agents can be assigned loads like [1,2,3,4,5] (15), [6,7] (13), [8] (8), [9] (9), [10] (10). All packages are distributed and max load is 15. Trying a smaller max load would require more than 5 agents.

3

Example 3

Input:

packageWeights = [100], numAgents = 1

Output:

100

Note:

Only one package and one agent, so the agent must carry the package weighing 100.

Constraints

Constraints & assumptions

  • 1 <= packageWeights.length <= 10^5
  • 1 <= packageWeights[i] <= 10^4
  • 1 <= numAgents <= packageWeights.length
  • The sum of all packageWeights will not exceed 10^9.

What interviewers evaluate

  • Algorithmic Approach: Ability to identify and apply binary search on the answer space.
  • Correctness of check function: Accurate implementation of the feasibility check (greedy approach).
  • Edge Cases: Handling scenarios like numAgents = 1 or numAgents = packageWeights.length.
  • Time and Space Complexity: Understanding and optimizing for the given constraints.

Loading editor...