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.
1#include <stdio.h>
2
3int maxSatisfied(int* customers, int customersSize, int* grumpy, int grumpySize, int minutes){
4 int total_satisfaction = 0, max_extra_satisfaction = 0, current_extra_satisfaction = 0;
5
6 // Calculate initial satisfaction for non-grumpy minutes
7 for (int i = 0; i < customersSize; ++i) {
8 if (!grumpy[i])
9 total_satisfaction += customers[i];
10 }
11
12 // Use sliding window to find max additional satisfaction in grumpy period
13 for (int i = 0; i < customersSize; ++i) {
14 if (grumpy[i]) {
15 current_extra_satisfaction += customers[i];
16 }
17 if (i >= minutes) {
18 if (grumpy[i - minutes])
19 current_extra_satisfaction -= customers[i - minutes];
20 }
21 if (current_extra_satisfaction > max_extra_satisfaction)
22 max_extra_satisfaction = current_extra_satisfaction;
23 }
24
25 return total_satisfaction + max_extra_satisfaction;
26}
27
28int main() {
29 int customers[] = {1, 0, 1, 2, 1, 1, 7, 5};
30 int grumpy[] = {0, 1, 0, 1, 0, 1, 0, 1};
31 int minutes = 3;
32 int result = maxSatisfied(customers, 8, grumpy, 8, minutes);
33 printf("Max satisfied customers: %d\n", result);
34 return 0;
35}This solution calculates the initial base satisfaction for all non-grumpy minutes. It then uses a sliding window to determine the maximum additional satisfaction from applying the no-grumpy technique over any possible time frame. The approach efficiently ensures a time complexity of O(n), only making a single linear traversal of the input.