Minimize cost & recommend movies

Question

Given arrays size[] and cost[] where size[i] is the size of the i-th product and cost[i] is the cost to increase size[i] by one unit, compute the minimal total cost required to increment elements so that all sizes become distinct.

Implement recommendMovies(userName) that returns a list of movie titles ordered by how frequently they were watched by the user’s friends and friends-of-friends, using Helper.getFriends and Helper.getMoviesWatched.

Min Cost to Make Sizes Distinct

You are given two arrays size and cost of equal length n. size[i] is the initial size of the i-th product, and cost[i] is the cost to increase size[i] by one unit. In one operation you may increase size[i] by 1, paying cost[i]. You cannot decrease any value. Compute the minimal total cost required to transform the array so that all final sizes are pairwise distinct integers.

Constraints

• 1 <= n <= 200000
• 0 <= size[i] <= 10^9
• 1 <= cost[i] <= 10^9
• Only increments are allowed
• Output may exceed 32-bit; use 64-bit integer arithmetic

Examples

Example 1

Input: size = [1,1,1], cost = [1,2,3]
Output: 4

Explanation: Assign final sizes [1,2,3]. Costs: 3*(1-1)=0, 2*(2-1)=2, 1*(3-1)=2; total = 4.

Example 2

Input: size = [2,2,1], cost = [100,1,1]
Output: 1

Explanation: Assign final sizes [1,2,3] by keeping expensive item at 2 and pushing a cheap item to 3. Total cost = 1.

Hints

1. Sort items by their initial size.
2. Sweep positions from left to right; at each integer position, at most one item can be assigned.
3. Maintain a max-heap (priority queue) of costs for items whose size is <= current position.
4. Greedily assign the current position to the item with the highest per-unit cost to avoid paying that cost in future increments.

Approach

Sort items by initial size s. Sweep integer positions pos from the smallest s upward. At each pos, consider all items with s <= pos as available and push them into a max-heap keyed by per-unit cost c. Assign the current position to the item with the highest c to avoid paying that cost in future increments, adding c * (pos - s) to the total. If no items are available, jump pos to the next start size. This greedy strategy is optimal by an exchange argument: if a cheaper item is chosen earlier than a more expensive one, swapping their assignments reduces or preserves cost.

• Time complexity: O(n log n)
• Space complexity: O(n)