Problem of The Day: Grumpy Bookstore Owner

Problem Statement

Intuition

My first thought on how to solve this problem is to maximize the number of satisfied customers by leveraging the non-grumpy minutes effectively. By using a sliding window approach, I can calculate the potential satisfaction increase within any minutes window, while maintaining the base satisfaction from non-grumpy customers.

Approach

1. Calculate the total number of satisfied customers without any intervention, which includes only the customers when the owner is not grumpy.
2. Use a sliding window of size minutes to find the maximum increase in satisfaction by turning the grumpy owner non-grumpy for that window duration.
3. The result will be the sum of the always satisfied customers and the maximum possible additional satisfied customers from the best window.

Complexity

• Time complexity: The time complexity of this approach is (O(n)), where (n) is the number of customers. This is because we only need to pass through the list a couple of times.
• Space complexity: The space complexity is (O(1)) since we only use a few extra variables regardless of the input size.

Code

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        n = len(customers)
        max_sum = 0
        total_satisfied = sum(customers[i] for i in range(n) if grumpy[i] == 0)
        for i in range(n - minutes + 1):
            curr_sum = sum(customers[i:i+minutes])
            curr_satisfied = sum(customers[i] for i in range(i, i + minutes) if grumpy[i] == 0)
            curr_sum += total_satisfied - curr_satisfied
            if curr_sum > max_sum:
                max_sum = curr_sum
        return max_sum

Editorial

class Solution:
    def maxSatisfied(
        self, customers: List[int], grumpy: List[int], minutes: int
    ) -> int:
        n = len(customers)
        unrealized_customers = 0

        # Calculate initial number of unrealized customers in first 'minutes' window
        for i in range(minutes):
            unrealized_customers += customers[i] * grumpy[i]

        max_unrealized_customers = unrealized_customers

        # Slide the 'minutes' window across the rest of the customers array
        for i in range(minutes, n):
            # Add current minute's unsatisfied customers if the owner is grumpy
            # and remove the customers that are out of the current window
            unrealized_customers += customers[i] * grumpy[i]
            unrealized_customers -= customers[i - minutes] * grumpy[i - minutes]

            # Update the maximum unrealized customers
            max_unrealized_customers = max(
                max_unrealized_customers, unrealized_customers
            )

        # Start with maximum possible satisfied customers due to secret technique
        total_customers = max_unrealized_customers

        # Add the satisfied customers during non-grumpy minutes
        for i in range(n):
            total_customers += customers[i] * (1 - grumpy[i])

        # Return the maximum number of satisfied customers
        return total_customers