1052. Grumpy Bookstore Owner

Description

There is a bookstore owner that has a store open for n minutes. Every minute, some number of customers enter the store. You are given an integer array customers of length n where customers[i] is the number of the customer that enters the store at the start of the ith minute and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. You are given a binary array grumpy where grumpy[i] is 1 if the bookstore owner is grumpy during the ith minute, and is 0 otherwise.

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 minutes consecutive minutes, 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], minutes = 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.

Example 2:

Input: customers = [1], grumpy = [0], minutes = 1
Output: 1

 

Constraints:

  • n == customers.length == grumpy.length
  • 1 <= minutes <= n <= 2 * 104
  • 0 <= customers[i] <= 1000
  • grumpy[i] is either 0 or 1.

Solutions

Solution 1

Python Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def maxSatisfied(
        self, customers: List[int], grumpy: List[int], minutes: int
    ) -> int:
        s = sum(a * b for a, b in zip(customers, grumpy))
        cs = sum(customers)
        t = ans = 0
        for i, (a, b) in enumerate(zip(customers, grumpy), 1):
            t += a * b
            if (j := i - minutes) >= 0:
                ans = max(ans, cs - (s - t))
                t -= customers[j] * grumpy[j]
        return ans

Java Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int s = 0, cs = 0;
        int n = customers.length;
        for (int i = 0; i < n; ++i) {
            s += customers[i] * grumpy[i];
            cs += customers[i];
        }
        int t = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            t += customers[i] * grumpy[i];
            int j = i - minutes + 1;
            if (j >= 0) {
                ans = Math.max(ans, cs - (s - t));
                t -= customers[j] * grumpy[j];
            }
        }
        return ans;
    }
}

C++ Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int s = 0, cs = 0;
        int n = customers.size();
        for (int i = 0; i < n; ++i) {
            s += customers[i] * grumpy[i];
            cs += customers[i];
        }
        int t = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            t += customers[i] * grumpy[i];
            int j = i - minutes + 1;
            if (j >= 0) {
                ans = max(ans, cs - (s - t));
                t -= customers[j] * grumpy[j];
            }
        }
        return ans;
    }
};

Go Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func maxSatisfied(customers []int, grumpy []int, minutes int) int {
	s, cs := 0, 0
	for i, c := range customers {
		s += c * grumpy[i]
		cs += c
	}
	t, ans := 0, 0
	for i, c := range customers {
		t += c * grumpy[i]
		j := i - minutes + 1
		if j >= 0 {
			ans = max(ans, cs-(s-t))
			t -= customers[j] * grumpy[j]
		}
	}
	return ans
}

Rust Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

impl Solution {
    pub fn max_satisfied(customers: Vec<i32>, grumpy: Vec<i32>, minutes: i32) -> i32 {
        let k = minutes as usize;
        let n = customers.len();

        let mut sum = 0;
        for i in 0..k {
            if grumpy[i] == 1 {
                sum += customers[i];
            }
        }
        let mut max = sum;
        for i in k..n {
            if grumpy[i - k] == 1 {
                sum -= customers[i - k];
            }
            if grumpy[i] == 1 {
                sum += customers[i];
            }
            max = max.max(sum);
        }

        sum = 0;
        for i in 0..n {
            if grumpy[i] == 0 {
                sum += customers[i];
            }
        }
        sum + max
    }
}