Question

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.

Like-time 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 like-time 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 like-time 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.

class Solution:
  def maxSatisfaction(self, satisfaction: List[int]) -> int:
    satisfaction.sort(reverse=True)
    ans = s = 0
    for x in satisfaction:
      s += x
      if s <= 0:
        break
      ans += s
    return ans

class Solution {
  public int maxSatisfaction(int[] satisfaction) {
    Arrays.sort(satisfaction);
    int ans = 0, s = 0;
    for (int i = satisfaction.length - 1; i >= 0; --i) {
      s += satisfaction[i];
      if (s <= 0) {
        break;
      }
      ans += s;
    }
    return ans;
  }
}

class Solution {
public:
  int maxSatisfaction(vector<int>& satisfaction) {
    sort(rbegin(satisfaction), rend(satisfaction));
    int ans = 0, s = 0;
    for (int x : satisfaction) {
      s += x;
      if (s <= 0) {
        break;
      }
      ans += s;
    }
    return ans;
  }
};

func maxSatisfaction(satisfaction []int) (ans int) {
  sort.Slice(satisfaction, func(i, j int) bool { return satisfaction[i] > satisfaction[j] })
  s := 0
  for _, x := range satisfaction {
    s += x
    if s <= 0 {
      break
    }
    ans += s
  }
  return
}

function maxSatisfaction(satisfaction: number[]): number {
  satisfaction.sort((a, b) => b - a);
  let [ans, s] = [0, 0];
  for (const x of satisfaction) {
    s += x;
    if (s <= 0) {
      break;
    }
    ans += s;
  }
  return ans;
}