Reducing dishes

Array Dynamic Programming Greedy Sorting

76.7% acceptance

Feb 25, 2026

3507

317

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_satisfaction(mut satisfaction: Vec<i32>) -> i32 {
    satisfaction.sort_unstable();
    let mut result = 0;
    let mut suffix_sum = 0;
    for &s in satisfaction.iter().rev() {
      suffix_sum += s;
      if suffix_sum <= 0 { break; }
      result += suffix_sum;
    }
    result
  }
}