Minimum Parcel Transfer Trips
A warehouse needs to move several parcels from its unloading area to its storage area.
A transfer trolley can move at most two parcels in one trip. Their combined weight must not exceed the trolley's maximum load.
Find the minimum number of trips needed to move every parcel.
Minimum Parcel Transfer Trips
Implement the following method:
int minimumTransferTrips( List<Integer> parcelWeights, int maximumLoad )
parcelWeights.get(i) is the weight of the ith parcel.maximumLoad is the maximum total weight allowed in one trolley trip.- The method returns the minimum number of trips required.
Rules
- Every parcel must be moved exactly once.
- Each trip must carry either one parcel or two parcels.
- The combined weight carried in a trip must not exceed
maximumLoad.
- Only trips carrying parcels are counted.
Constraints
1 ≤ parcelWeights.size() ≤ 100,000 1 ≤ parcelWeights.get(i) ≤ maximumLoad 1 ≤ maximumLoad ≤ 1,000,000,000parcelWeights never contains null values.
Examples
Example 1
minimumTransferTrips( parcelWeights = List.of(29, 34, 47, 68), maximumLoad = 80 )
Output: 3
The parcels weighing 29 and 47 can travel together. The other two parcels require separate trips.
Example 2
minimumTransferTrips( parcelWeights = List.of(22, 28, 32, 38), maximumLoad = 60 )
Output: 2
The parcels can be grouped as 22 + 38 and 28 + 32.
Example 3
minimumTransferTrips( parcelWeights = List.of(46, 47, 48, 49), maximumLoad = 90 )
Output: 4
Every pair exceeds the maximum load, so each parcel requires its own trip.
Example 4
minimumTransferTrips( parcelWeights = List.of(15, 25, 35, 45, 55), maximumLoad = 70 )
Output: 3
The parcels can be grouped as 15 + 55, 25 + 45, and 35 by itself.