Maximize efficiency for this LeetCode style problem [duplicate]

Question

I found this LeetCode style problem in a previous assignment for my university.

Assume you have an online clothing store and you have products which come in variable sizes. Some products come in the same size multiple times, and you don't want to have any duplicates. Assume the sizes of the products are kept in an array size, of size n. The price of increasing each size[i] by 1 is indicated in the array costs[i]; What is the minimum cost you need to make all sizes unique? For example, if you have the array size = [3,3,4,5] and costs = [5,2,3,1], the minimum cost is 5 in order to modify the array to [3,5,4,6] (modify the second 3 twice and the 5 once: 2*2 + 1 = 5).

I implemented a solution where I have a priority queue where I store all size & cost pairs, ordered by cost descending. The code is similar to the following pseudocode:

var uniqueSizes = new HashSet<int>(); // maintain all unique sizes in a set
int totalCost = 0;
while (pq.Count > 0){
    currentPair = pq.Dequeue();
    currentSize = currentPair.Item1, currentCost = currentPair.Item2;
    while(uniqueSizes.Contains(currentSize){ 
      // keep increasing until I find a size that is not in the set
       currentSize++;
       totalCost += currentCost;
   }
   
   uniqueSizes.Add(currentSize);
}

return totalCost;

My code does run on all tests, but it exceeds time limit on some. I expect that is because I could not find a way to replace the inner while loop, where I keep increasing the currentSize until I find one that is not in the set. I would appreciate any suggestions to make this more time efficient or any alternative solutions which perform in less than O(n^2).

I also expect the code I provided to run in O(n^2) in worst case (outer while: O(n); inner while: worst case, when adding the nth item I need to increase the size n-1 times). Is this assumption correct?

Note: you can solve this in any language you want / even pseudocode, I only care about the algorithm or idea

Answer 1

Each element needs to exist from [mn, mn + n - 1] where mn is the minimum element in sizes and n is the length of the array. Therefore, we should try moving elements with the smallest cost. Since sizes needs to be unique, we should only keep the max cost at a specific size to minimize the total cost.

Store all the costs associated with the current size into a priority queue while keeping a running total. Pop the top of the priority queue and remove that cost from the running total while adding the rest to the total cost. Done for each size by iterating over [mn, mn + n - 1]. This runs in O(nlogn).