Grumpy Bookstore Owner

LeetCode Q 1052 - Grumpy Bookstore Owner

Today, the bookstore owner has a store open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

Example 1:
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3 ; Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes.
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

Note:

• 1 <= X <= customers.length == grumpy.length <= 20000
• 0 <= customers[i] <= 1000
• 0 <= grumpy[i] <= 1

Solution

• Use var satisfy to track the total number of customers that the ower is not angry.
• Use var window to record the increased number of customers through using the magic within X minutes.
• Use var max to track the maximum window.

How to update satisfy and window?

• satisfy: Sum(customers[i]), where grumpy[i] = 0.
• window: use sliding window algorithm.

Code:

public int maxSatisfied(int[] customers, int[] grumpy, int X) {
	
	int window = 0, satisfy = 0, max = 0;

	for (int i = 0; i < customers.length; i++) {
		if (grumpy[i] == 0)
			satisfy += customers[i];
		else if
			window += customers[i];

		if (i >= X)
			window -= customers[i - X] * grumpy[i - X];
	
		max = Math.max(max, window);
	}

	return satisfy + max;
}