Grumpy Bookstore Owner

Problem

A bookstore owner is grumpy on some minutes, losing those customers. Using a special technique for X consecutive minutes removes grumpiness during that window. Find the maximum number of satisfied customers possible.

Input:  customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
Output: 16

Python Solution

def max_satisfied(customers, grumpy, minutes):
    base = sum(c for c, g in zip(customers, grumpy) if g == 0)
    window_gain = sum(customers[i] * grumpy[i] for i in range(minutes))
    best_gain = window_gain
    for i in range(minutes, len(customers)):
        window_gain += customers[i] * grumpy[i] - customers[i - minutes] * grumpy[i - minutes]
        best_gain = max(best_gain, window_gain)
    return base + best_gain

C++ Solution

int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
    int base = 0;
    for (int i = 0; i < customers.size(); i++) {
        if (grumpy[i] == 0) base += customers[i];
    }
    int windowGain = 0;
    for (int i = 0; i < minutes; i++) windowGain += customers[i] * grumpy[i];
    int bestGain = windowGain;
    for (int i = minutes; i < customers.size(); i++) {
        windowGain += customers[i] * grumpy[i] - customers[i - minutes] * grumpy[i - minutes];
        bestGain = max(bestGain, windowGain);
    }
    return base + bestGain;
}

Java Solution

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int base = 0;
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 0) base += customers[i];
        }
        int windowGain = 0;
        for (int i = 0; i < minutes; i++) windowGain += customers[i] * grumpy[i];
        int bestGain = windowGain;
        for (int i = minutes; i < customers.length; i++) {
            windowGain += customers[i] * grumpy[i] - customers[i - minutes] * grumpy[i - minutes];
            bestGain = Math.max(bestGain, windowGain);
        }
        return base + bestGain;
    }
}

Complexity

Time: O(n) — one pass to compute the base satisfaction, one sliding pass to find the best extra gain. Space: O(1) — only running sums are tracked.