Amazon ships millions of packages regularly. There are a number of parcels that need to be shipped. Compute the minimum possible sum of transportation costs incurred in the shipment of additional parcels in the following scenario.
• A fully loaded truck carries k parcels.
• It is most efficient for the truck to be fully loaded.
• There are a number of parcels already on the truck as listed in parcels/. • There are parcels with a unique id that ranges from 1 through infinity.
• The parcel id is also the cost to ship that parcel.
Given the parcel IDs which are already added in the shipment, find the minimum possible cost of shipping the items added to complete the load.
Constraints
- 1 <= n <= 2 * 10^5
- 1 <= parcels[I] <= 10^6
- n<= k<10^6
Input Format For Custom Testing
The first line contains an integer, n, the size of parcels. Each line i of the n subsequent lines (where 0 <i <n) contains an integer, parcels. The last line contains the integer k the capacity of the truck.
Example
Example
parcels = [2, 3, 6, 10, 11]
k=9
Parcel ids range from 1 through infinity. After reviewing the current manifest, the remaining parcels to choose from are [1, 4, 5, 7, 8, 9, 12, 13, …]. There are 5 parcels already on the truck, and it can carry k = 9 parcels when fully loaded. Choose 4 more packages to include: [1, 4, 5, 7J. Their shipping cost is 1 +4 +5 ÷ 7= 77, which is minimal. Return 17.
Python Code
def getifinimumCost(parcels, k):
i=1
cost = 0
parcels.sort()
j=0
while len(parcels)= len(parcels):
cost += i
k-=1
j+=1
i+=1
elif parcels[j]>i:
cost += i
k-=1
i+=1
else: i+=1
returncost