Maximum Profit of Operating a Centennial Wheel

Problem Description

You are the operator of a Centennial Wheel that has four gondolas, and each gondola has room for up to four people. You have the ability to rotate the gondolas counterclockwise, which costs you runningCost dollars. You are given an array customers of length n where customers[i] is the number of new customers arriving just before the i-th rotation (0-indexed). This means you must rotate the wheel i times before the customers[i] customers arrive. You cannot make customers wait if there is room in the gondola. Each customer pays boardingCost dollars when they board on the gondola closest to the ground and will exit once that gondola reaches the ground again. You can stop the wheel at any time, including before serving all customers. If you decide to stop serving customers, all subsequent rotations are free in order to get all the customers down safely. Note that if there are currently more than four customers waiting at the wheel, only four will board the gondola, and the rest will wait for the next rotation. Return the minimum number of rotations you need to perform to maximize your profit. If there is no scenario where the profit is positive, return -1.

Key Insights

• Each gondola can hold up to 4 customers, and only 4 will board in case of overflow.
• Profit is calculated as the difference between the total income from boarding customers and the running cost of the rotations.
• The decision to stop rotations can lead to maximizing profit, especially when the cost of running the wheel exceeds the income.
• A sliding window or prefix sum approach can be useful for tracking the total number of customers and profit over the rotations.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can simulate the process of boarding customers and calculate the profit after each rotation. We maintain a running total of the number of customers that have boarded and a queue to manage the customers waiting. We also keep track of the best profit observed and the corresponding number of rotations. If at any point the profit becomes negative and does not recover, we can stop and return -1.

1. Use a loop to iterate through the customers array.
2. For each rotation, calculate how many customers can board based on the total waiting.
3. Update the profit using the formula: profit = (total boarded customers * boardingCost) - (current rotations * runningCost).
4. Track the maximum profit and the minimum rotations needed to achieve that profit.

Code Solutions