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.
1public class MaxSatisfied {
2 public static int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
3 int totalSatisfaction = 0, maxExtraSatisfaction = 0, currentExtraSatisfaction = 0;
4 int n = customers.length;
5
6 for (int i = 0; i < n; ++i) {
7 if (grumpy[i] == 0) {
8 totalSatisfaction += customers[i];
9 }
10 }
11
12 for (int i = 0; i < n; ++i) {
13 if (grumpy[i] == 1) {
14 currentExtraSatisfaction += customers[i];
15 }
16 if (i >= minutes) {
17 if (grumpy[i - minutes] == 1) {
18 currentExtraSatisfaction -= customers[i - minutes];
19 }
20 }
21 maxExtraSatisfaction = Math.max(maxExtraSatisfaction, currentExtraSatisfaction);
22 }
23
24 return totalSatisfaction + maxExtraSatisfaction;
25 }
26
27 public static void main(String[] args) {
28 int[] customers = {1, 0, 1, 2, 1, 1, 7, 5};
29 int[] grumpy = {0, 1, 0, 1, 0, 1, 0, 1};
30 int minutes = 3;
31 System.out.println("Max satisfied customers: " + maxSatisfied(customers, grumpy, minutes));
32 }
33}This Java solution involves iterating through the customers and grumpy arrays while using a sliding window to determine the largest amount of additional satisfaction achievable by deploying the no-grumpy technique. This approach optimizes performance to achieve a linear runtime complexity.