Package Sorting with Weight Constraints

Problem Statement

Amazon's fulfillment center receives N packages with weights w[i]. Each delivery truck has a maximum capacity C. Minimize the number of trucks needed to ship all packages, where a truck can carry multiple packages as long as their total weight ≤ C. You may assume each package weight ≤ C.

Company Use Case

Amazon uses this exact algorithm in their fulfillment centers worldwide. During peak seasons like Prime Day, the system processes millions of packages per hour, assigning them to delivery trucks while minimizing the fleet size. The two-pointer greedy approach saves Amazon millions in logistics costs annually.

Examples

weights = [4, 8, 1, 4, 2, 1], C = 10

3

weights = [2, 3, 4, 5], C = 5

3

Constraints

• •1 ≤ N ≤ 10^5
• •1 ≤ w[i] ≤ C ≤ 10^9
• •Each package fits in at least one truck (w[i] ≤ C)