LeetCode 1648: Sell Diminishing-Valued Colored Balls
Problem Description
Explanation
To maximize the total value obtained from selling colored balls, we need to prioritize selling balls with higher values first. We can achieve this by simulating the selling process. We can keep track of the number of balls sold for each color and update the value of the remaining balls accordingly. We sort the inventory in descending order to start selling the balls with the highest value.
The algorithm involves the following steps:
- Sort the inventory in descending order.
- Initialize variables for total value, current color index, and current color count.
- While the total number of orders is greater than 0:
- Get the current color count by taking the difference between the current color and the next color in the inventory.
- Calculate the number of balls to sell based on the current color count and the remaining orders.
- Update the total value by selling the calculated number of balls.
- Update the current color count and the remaining orders.
- Move to the next color in the inventory.
The time complexity of this algorithm is O(n log n) due to the sorting step, where n is the number of colors in the inventory. The space complexity is O(1) as we are not using any extra space proportional to the input size.
Solutions
class Solution {
public int maxProfit(int[] inventory, int orders) {
Arrays.sort(inventory);
long totalValue = 0;
int n = inventory.length;
int mod = 1000000007;
int i = n - 1;
int currColor = inventory[i];
while (orders > 0) {
int count = 1;
while (i > 0 && inventory[i - 1] == currColor) {
i--;
count++;
}
int diff = currColor - (i == 0 ? 0 : inventory[i - 1]);
if (orders >= count * diff) {
long sell = (long) count * (2 * currColor - diff + 1) * diff / 2;
totalValue = (totalValue + sell) % mod;
orders -= count * diff;
} else {
long fullRows = orders / count;
long remainder = orders % count;
long sell = (long) count * (currColor + currColor - fullRows + 1) * fullRows / 2 +
(long) remainder * (currColor - fullRows);
totalValue = (totalValue + sell) % mod;
orders = 0;
}
currColor = i == 0 ? 0 : inventory[i - 1];
}
return (int) totalValue;
}
}Loading editor...