FastPrep
Problem · Array

Minimize Maximum Parcels

Learn this problem
● MediumAmazonNEW GRADINTERNOA
See Amazon hiring insights

Problem statement

You are give:

  • An integer array packages[i], where each element represents the number of packages currently assigned to the i-th delivery center.
  • An integer extra_packages, which denotes the total number of additional packages that must be distributed among the delivery centers.

    • Our mission this time is to help the company calculate the minimum possible value of the maximum number of packages assigned to any delivery center after distributing all the extra packages optimally.

    Function

    minimizeMaximumParcels(packages: int[], extra_packages: long) → long

    Examples

    Example 1

    packages = [7, 5, 1, 9, 1]extra_packages = 25return = 10

    With packages = [7, 5, 1, 9, 1] and extra_packages = 25, the goal is to make the maximum as small as possible.

    If we set a cap of 10, the additional packages needed to raise each center up to 10 are (10-7) + (10-5) + (10-1) + (10-9) + (10-1) = 3 + 5 + 9 + 1 + 9 = 27, which is at least the 25 extra packages available, so a maximum of 10 is achievable.

    One optimal assignment uses exactly 25 extra packages: add 3, 5, 9, 1, and 8 to the centers respectively, giving totals [10, 10, 10, 10, 9]. The maximum is 10.

    A cap of 9 would require (9-7) + (9-5) + (9-1) + (9-1) = 2 + 4 + 8 + 8 = 22 just to bring the four under-9 centers up to 9, but center 4 already holds 9 and cannot be lowered, and distributing all 25 extra packages forces at least one center above 9. Therefore 9 is not achievable, and the answer is 10.

    Example 2

    packages = [1, 2, 3]extra_packages = 3return = 3
    Assign two extra pacakges to the 1st delivery center and one extra to the second center. Eventually, each center will have to send three packages. (Added on 2025-02-15)

    Example 3

    packages = [1]extra_packages = 3return = 4
    Because we have only 1 delivery center, all the extra packages will be assigned to the same :) (Added on 2025-02-15)

    Constraints

    • 1 <= packages.length <= 105
    • 1 <= packages[i] <= 109
    • 1 <= extra_packages <= 1015
    • The return value may exceed 32-bit integer range and should be treated as a 64-bit integer.

    More Amazon problems

    drafts saved locally
    public long minimizeMaximumParcels(int[] packages, long extraParcels) {
  // write your code here
}
    packages[7, 5, 1, 9, 1]
    extra_packages25
    expected10
    checking account