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 <iostream>
2#include <vector>
3
4using namespace std;
5
6int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
7 int total_satisfaction = 0, max_extra_satisfaction = 0, current_extra_satisfaction = 0;
8 int n = customers.size();
9
10 for (int i = 0; i < n; ++i) {
11 if (!grumpy[i])
12 total_satisfaction += customers[i];
13 }
14
15 for (int i = 0; i < n; ++i) {
16 if (grumpy[i]) {
17 current_extra_satisfaction += customers[i];
18 }
19 if (i >= minutes) {
20 if (grumpy[i - minutes])
21 current_extra_satisfaction -= customers[i - minutes];
22 }
23 max_extra_satisfaction = max(max_extra_satisfaction, current_extra_satisfaction);
24 }
25
26 return total_satisfaction + max_extra_satisfaction;
27}
28
29int main() {
30 vector<int> customers = {1, 0, 1, 2, 1, 1, 7, 5};
31 vector<int> grumpy = {0, 1, 0, 1, 0, 1, 0, 1};
32 int minutes = 3;
33 cout << "Max satisfied customers: " << maxSatisfied(customers, grumpy, minutes) << endl;
34 return 0;
35}The solution starts by computing the total number of satisfied customers when the owner is not grumpy. It then slides a window over the period where the owner is grumpy to calculate the best possible additional satisfaction gain. It's efficient with a time complexity of O(n).