Reducing Dishes Problem

Problem

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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3
4
5

Input:
satisfaction = [4,3,2]
Output:
 20
Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)

Example 3:

1
2
3
4
5

Input:
satisfaction = [-1,-4,-5]
Output:
 0
Explanation: People do not like the dishes. No dish is prepared.

Solution

Method 1 – Greedy with Sorting

Intuition

Sort the satisfaction levels in descending order. Add dishes one by one from highest satisfaction, and keep track of the running sum. If adding a dish increases the total like-time coefficient, keep it; otherwise, stop.

Approach

  1. Sort satisfaction in descending order.
  2. Initialize total and running sum to 0.
  3. For each dish, add its satisfaction to running sum.
  4. If running sum is positive, add it to total; else, break.
  5. Return total.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.rbegin(), satisfaction.rend());
        int total = 0, run = 0;
        for (int x : satisfaction) {
            run += x;
            if (run > 0) total += run;
            else break;
        }
        return total;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func maxSatisfaction(satisfaction []int) int {
    sort.Sort(sort.Reverse(sort.IntSlice(satisfaction)))
    total, run := 0, 0
    for _, x := range satisfaction {
        run += x
        if run > 0 {
            total += run
        } else {
            break
        }
    }
    return total
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);
        int total = 0, run = 0;
        for (int i = satisfaction.length-1; i >= 0; --i) {
            run += satisfaction[i];
            if (run > 0) total += run;
            else break;
        }
        return total;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun maxSatisfaction(satisfaction: IntArray): Int {
        satisfaction.sortDescending()
        var total = 0
        var run = 0
        for (x in satisfaction) {
            run += x
            if (run > 0) total += run
            else break
        }
        return total
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def maxSatisfaction(self, satisfaction: list[int]) -> int:
        satisfaction.sort(reverse=True)
        total = run = 0
        for x in satisfaction:
            run += x
            if run > 0:
                total += run
            else:
                break
        return total
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn max_satisfaction(mut satisfaction: Vec<i32>) -> i32 {
        satisfaction.sort_by(|a, b| b.cmp(a));
        let mut total = 0;
        let mut run = 0;
        for x in satisfaction {
            run += x;
            if run > 0 {
                total += run;
            } else {
                break;
            }
        }
        total
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    maxSatisfaction(satisfaction: number[]): number {
        satisfaction.sort((a, b) => b - a)
        let total = 0, run = 0
        for (const x of satisfaction) {
            run += x
            if (run > 0) total += run
            else break
        }
        return total
    }
}

Complexity

  • ⏰ Time complexity: O(n log n) — Sorting and single pass.
  • 🧺 Space complexity: O(1) — In-place sorting and variables only.