LeetCode 1599: Maximum Profit of Operating a Centennial Wheel

Explanation

To maximize profit, we need to carefully manage the rotation of the Centennial Wheel to ensure that we serve customers efficiently. We can simulate the process by keeping track of the number of customers waiting at each rotation and calculating the profit at each step. The goal is to find the minimum number of rotations that maximize profit or return -1 if no positive profit scenario exists.

Here is the algorithm:

1. Initialize variables for total customers served, total profit, and current profit.
2. Iterate through the customers array:
   • Update the total customers served.
   • Check if there are more than 4 customers waiting. If so, only consider the first 4 customers to board.
   • Calculate the profit for the current rotation based on the boarding cost and running cost.
   • Update the total profit and current profit.
   • If the current profit is greater than the maximum profit seen so far, update the maximum profit.
3. Return the minimum number of rotations required to achieve the maximum profit, or -1 if no positive profit scenario exists.

Time complexity: O(n) where n is the number of elements in the customers array. Space complexity: O(1)

class Solution {
    public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
        int totalCustomers = 0;
        int totalProfit = 0;
        int currentProfit = 0;
        int maxProfit = 0;
        int rotations = 0;
        
        int i = 0;
        while (totalCustomers > 0 || i < customers.length) {
            if (i < customers.length) {
                totalCustomers += customers[i];
            }
            
            int boarding = Math.min(4, totalCustomers);
            totalCustomers -= boarding;
            currentProfit += boarding * boardingCost - runningCost;
            
            rotations++;
            if (currentProfit > maxProfit) {
                maxProfit = currentProfit;
                rotations = 0;
            }
            
            totalProfit += currentProfit;
            i++;
        }
        
        return maxProfit > 0 ? rotations : -1;
    }
}