Solution Explanation: 1402. Reducing Dishes

This problem asks to find the maximum sum of "like-time coefficients" achievable by preparing a subset of dishes. The like-time coefficient of a dish is its satisfaction level multiplied by its preparation time (which is its index plus 1, assuming 1-based indexing). The key insight is that a greedy approach, combined with sorting, provides an efficient solution.

Approach: Greedy with Sorting

1. Sorting: The most crucial step is sorting the satisfaction array in descending order. This prioritizes dishes with higher satisfaction levels.

2. Greedy Selection: We iterate through the sorted array. For each dish, we calculate its contribution to the total satisfaction. This contribution is the sum of the dish's satisfaction and the satisfaction of all dishes already selected, multiplied by the dish's preparation time.

3. Stopping Condition: If, at any point, adding the next dish reduces the total satisfaction, we stop. This is because including less satisfying dishes with later preparation times will always lower the overall "like-time coefficient."

4. Return Value: The maximum total "like-time coefficient" accumulated during the iteration is the final answer.

Time and Space Complexity Analysis

• Time Complexity: The dominant operation is the sorting of the satisfaction array, which takes O(n log n) time, where n is the number of dishes. The subsequent iteration through the sorted array takes O(n) time. Therefore, the overall time complexity is O(n log n).

• Space Complexity: The sorting algorithm might use extra space depending on the implementation (e.g., merge sort uses O(n) space, while heapsort uses O(1) space). However, if we ignore the space used by the input array, the additional space used by the algorithm is O(log n) or O(1), depending on the sorting algorithm used.

Code Examples (Python, Java, C++, Go, TypeScript)

The code examples below demonstrate the greedy approach with sorting:

Python:

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

Java:

import java.util.Arrays;
 
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;
    }
}

C++:

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

Go:

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

TypeScript:

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

These codes all implement the same greedy strategy and achieve the optimal solution efficiently. The slight variations reflect the syntactic differences between the programming languages.