Maximum Satisfaction (LeetCode 1402) – Greedy Algorithm Solution

A chef has n dishes, each with a satisfaction value. Cooking each dish takes one unit of time, and the "like time" for a dish is defined as the time at which it is cooked multiplied by its satisfaction value. The goal is to order (or discard) dishes to maximize the sum of all like times.

Example 1: satisfaction = [-1, -8, 0, 5, -9] → maximum like‑time sum is 14 by discarding the second and last dishes, giving (-1*1 + 0*2 + 5*3 = 14) .

Example 2: satisfaction = [4, 3, 2] → maximum sum is 20 by cooking in reverse order: 2*1 + 3*2 + 4*3 = 20 .

Example 3: satisfaction = [-1, -4, -5] → all values are negative, so the optimal choice is to cook nothing, yielding a sum of 0 .

The greedy solution sorts the satisfaction array in ascending order and processes it from the end, maintaining a suffix sum of the remaining values. As long as the suffix sum is positive, it contributes to the result; once it becomes non‑positive, further additions would only decrease the total, so the algorithm stops.

Java implementation:

public int maxSatisfaction(int[] satisfaction) {
    // Sort the array first
    Arrays.sort(satisfaction);
    int afterSum = 0; // suffix sum
    int res = 0; // result
    for (int i = satisfaction.length - 1; i >= 0; i--) {
        // accumulate suffix sum
        afterSum += satisfaction[i];
        // if suffix sum is non‑positive, stop
        if (afterSum <= 0) {
            return res;
        }
        // add current suffix sum to result
        res += afterSum;
    }
    return res;
}