1052. Grumpy Bookstore Owner #

Problem #

Today, the bookstore owner has a store open for customers.lengthminutes. 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

Problem Summary #

Today, the bookstore owner has a store that plans to be open for a trial run for customers.length minutes. Every minute, some customers (customers[i]) enter the bookstore, and all these customers leave after that minute ends. At certain times, the bookstore owner gets angry. If the bookstore owner is angry during the i-th minute, then grumpy[i] = 1; otherwise grumpy[i] = 0. When the bookstore owner is angry, the customers during that minute are dissatisfied; when not angry, they are satisfied. The bookstore owner knows a secret technique that can suppress their emotions, allowing them to not be angry for X consecutive minutes, but it can only be used once. Please return the maximum number of customers who can be satisfied over the course of the day.

Note:

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

Solution Approach #

Given a customer entry schedule and the bookstore owner’s temper schedule. The times of the two arrays correspond one-to-one, meaning the same index corresponds to the same time. The bookstore owner can control themselves and not get angry for X minutes, but can only do so once. Ask how many customers can be in the bookstore reading when the bookstore owner is not angry. Abstractly, given a value array and an array containing 0s and 1s: when the value at an index in the value array corresponds to a 0 at the same index in the other array, that value can be accumulated; when it corresponds to 1, that value cannot be added. Now you can make X consecutive numbers in the array containing 0s and 1s all become 0. What is the maximum final value?
This problem is a typical sliding window problem. The most brute-force solution is to slide the right boundary of the window, and when the distance from the left boundary equals X, calculate the total value of the corresponding array at that moment. After the entire window of width X slides through the whole array, output the maintained maximum value. This method takes relatively long because each time the total value of the array is calculated, the entire array must be traversed. This is where optimization is possible.
Each time the total value of the array is calculated, the actual goal is to find the maximum sum of the values corresponding to the 1s inside the window of width X, because if all the 1s inside this window are changed to 0s, the impact on the final value is the greatest. So use a variable customer0 specifically to record and accumulate the values corresponding to 0s in the temper array. No matter how it changes, 0s will always remain 0s; the only change is that 1s become 0s. Use customer1 specifically to record the values corresponding to 1s in the temper array. Find the maximum value of customer1 during the window sliding process. The final required maximum value is customer0 + maxCustomer1.

Code #


package leetcode

// Solution 1: optimized sliding window version
func maxSatisfied(customers []int, grumpy []int, X int) int {
	customer0, customer1, maxCustomer1, left, right := 0, 0, 0, 0, 0
	for ; right < len(customers); right++ {
		if grumpy[right] == 0 {
			customer0 += customers[right]
		} else {
			customer1 += customers[right]
			for right-left+1 > X {
				if grumpy[left] == 1 {
					customer1 -= customers[left]
				}
				left++
			}
			if customer1 > maxCustomer1 {
				maxCustomer1 = customer1
			}
		}
	}
	return maxCustomer1 + customer0
}

// Solution 2: brute-force sliding window version
func maxSatisfied1(customers []int, grumpy []int, X int) int {
	left, right, res := 0, -1, 0
	for left < len(customers) {
		if right+1 < len(customers) && right-left < X-1 {
			right++
		} else {
			if right-left+1 == X {
				res = max(res, sumSatisfied(customers, grumpy, left, right))
			}
			left++
		}
	}
	return res
}

func sumSatisfied(customers []int, grumpy []int, start, end int) int {
	sum := 0
	for i := 0; i < len(customers); i++ {
		if i < start || i > end {
			if grumpy[i] == 0 {
				sum += customers[i]
			}
		} else {
			sum += customers[i]
		}
	}
	return sum
}