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.
1def max_satisfied(customers, grumpy, minutes):
2 total_satisfaction = sum(c for c, g in zip(customers, grumpy) if not g)
3 max_extra_satisfaction = current_extra_satisfaction = 0
4
5 for i in range(len(customers)):
6 if grumpy[i]:
7 current_extra_satisfaction += customers[i]
8 if i >= minutes and grumpy[i - minutes]:
9 current_extra_satisfaction -= customers[i - minutes]
10 max_extra_satisfaction = max(max_extra_satisfaction, current_extra_satisfaction)
11
12 return total_satisfaction + max_extra_satisfaction
13
14customers = [1, 0, 1, 2, 1, 1, 7, 5]
15grumpy = [0, 1, 0, 1, 0, 1, 0, 1]
16minutes = 3
17result = max_satisfied(customers, grumpy, minutes)
18print(f'Max satisfied customers: {result}')In this Python solution, the key insight is to split the problem into two parts: calculate base satisfaction for non-grumpy periods and find the maximum possible additional satisfaction using a sliding window over the grumpy periods. The approach pursues an O(n) time complexity by efficiently leveraging the zip function and sliding window technique.