Sponsored
Sponsored
This approach uses the sliding window technique to maximize the number of satisfied customers by calculating the additional satisfaction obtained by using the non-grumpy technique for a given number of consecutive minutes.
Time Complexity: O(n), as it involves a single pass through the arrays.
Space Complexity: O(1), as no extra space beyond a few variables is used.
1function maxSatisfied(customers, grumpy, minutes) {
2 let totalSatisfaction = 0, maxExtraSatisfaction = 0, currentExtraSatisfaction = 0;
3
4 for (let i = 0; i < customers.length; i++) {
5 if (grumpy[i] === 0) {
6 totalSatisfaction += customers[i];
7 }
8 }
9
10 for (let i = 0; i < customers.length; i++) {
11 if (grumpy[i] === 1) {
12 currentExtraSatisfaction += customers[i];
13 }
14 if (i >= minutes && grumpy[i - minutes] === 1) {
15 currentExtraSatisfaction -= customers[i - minutes];
16 }
17 maxExtraSatisfaction = Math.max(maxExtraSatisfaction, currentExtraSatisfaction);
18 }
19
20 return totalSatisfaction + maxExtraSatisfaction;
21}
22
23const customers = [1, 0, 1, 2, 1, 1, 7, 5];
24const grumpy = [0, 1, 0, 1, 0, 1, 0, 1];
25const minutes = 3;
26console.log(`Max satisfied customers: ${maxSatisfied(customers, grumpy, minutes)}`);This JavaScript solution iteratively calculates the base satisfaction and employs a sliding window to determine the optimal period for increased satisfaction by covering grumpy spans efficiently, reaching an O(n) time complexity.