1402. Reducing Dishes
Description
A chef has collected data on the satisfaction
level of his n
dishes. Chef can cook any dish in 1 unit of time.
Liketime coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. time[i] * satisfaction[i]
.
Return the maximum sum of liketime coefficient that the chef can obtain after preparing some amount of dishes.
Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.
Example 1:
Input: satisfaction = [1,8,0,5,9] Output: 14 Explanation: After Removing the second and last dish, the maximum total liketime coefficient will be equal to (1*1 + 0*2 + 5*3 = 14). Each dish is prepared in one unit of time.
Example 2:
Input: satisfaction = [4,3,2] Output: 20 Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)
Example 3:
Input: satisfaction = [1,4,5] Output: 0 Explanation: People do not like the dishes. No dish is prepared.
Constraints:
n == satisfaction.length
1 <= n <= 500
1000 <= satisfaction[i] <= 1000
Solutions
Solution 1: Greedy + Sorting
Suppose we only choose one dish, then we should choose the dish with the highest satisfaction $s_0$, and check whether $s_0$ is greater than 0. If $s_0 \leq 0$, then we don’t cook any dishes, otherwise, we cook this dish, and the total satisfaction is $s_0$.
If we choose two dishes, then we should choose the two dishes with the highest satisfaction $s_0$ and $s_1$, and the satisfaction is $s_1 + 2 \times s_0$. At this time, we need to ensure that the satisfaction after the selection is greater than the satisfaction before the selection, that is, $s_1 + 2 \times s_0 > s_0$, which means as long as $s_1 + s_0 > 0$, we can choose these two dishes.
By analogy, we can find a rule, that is, we should choose the $k$ dishes with the highest satisfaction, and ensure that the sum of the satisfaction of the first $k$ dishes is greater than $0$.
In implementation, we can first sort the satisfaction of all dishes, and then start choosing from the dish with the highest satisfaction. Each time we add the satisfaction of the current dish, if the result of the addition is less than or equal to $0$, then we no longer choose the dishes behind, otherwise, we choose this dish.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Where $n$ is the length of the array.









