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.
1using System;
2
3public class MaxSatisfied {
4 public static int MaxSatisfiedCustomers(int[] customers, int[] grumpy, int minutes) {
5 int totalSatisfaction = 0, maxExtraSatisfaction = 0, currentExtraSatisfaction = 0;
6 int n = customers.Length;
7
8 for (int i = 0; i < n; ++i) {
9 if (grumpy[i] == 0) {
10 totalSatisfaction += customers[i];
11 }
12 }
13
14 for (int i = 0; i < n; ++i) {
15 if (grumpy[i] == 1) {
16 currentExtraSatisfaction += customers[i];
17 }
18 if (i >= minutes) {
19 if (grumpy[i - minutes] == 1) {
20 currentExtraSatisfaction -= customers[i - minutes];
21 }
22 }
23 maxExtraSatisfaction = Math.Max(maxExtraSatisfaction, currentExtraSatisfaction);
24 }
25
26 return totalSatisfaction + maxExtraSatisfaction;
27 }
28
29 public static void Main() {
30 int[] customers = {1, 0, 1, 2, 1, 1, 7, 5};
31 int[] grumpy = {0, 1, 0, 1, 0, 1, 0, 1};
32 int minutes = 3;
33 Console.WriteLine("Max satisfied customers: " + MaxSatisfiedCustomers(customers, grumpy, minutes));
34 }
35}This C# solution employs a sliding window to manage the range across which the bookstore owner can remain non-grumpy. The solution effectively computes the best possible gain in customer satisfaction over this period, ensuring consistent runtime efficiency with a linear time complexity.