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

Rust Solution

struct Solution;

use std::i32;

impl Solution {
    fn max_satisfied(customers: Vec<i32>, grumpy: Vec<i32>, x: i32) -> i32 {
        let mut sum = 0;
        let mut max = 0;
        let n = customers.len();
        for i in 0..n {
            if grumpy[i] == 0 {
                sum += customers[i];
            }
        }
        let x = x as usize;
        for i in 0..x {
            if grumpy[i] == 1 {
                sum += customers[i];
            }
        }
        max = i32::max(sum, max);
        for i in x..n {
            if grumpy[i] == 1 {
                sum += customers[i];
            }
            if grumpy[i - x] == 1 {
                sum -= customers[i - x];
            }
            max = i32::max(sum, max);
        }
        max
    }
}

#[test]
fn test() {
    let customers = vec![1, 0, 1, 2, 1, 1, 7, 5];
    let grumpy = vec![0, 1, 0, 1, 0, 1, 0, 1];
    let x = 3;
    let res = 16;
    assert_eq!(Solution::max_satisfied(customers, grumpy, x), res);
}

Having problems with this solution? Click here to submit an issue on github.