#1599

Medium

LeetCode Problem Workspace

Maximum Profit of Operating a Centennial Wheel

Maximize the profit from operating a Centennial Wheel by determining the optimal number of rotations based on customer arrivals, boarding cost, and running cost.

array simulation

Problem Statement

You are operating a Centennial Wheel with four gondolas, each holding up to four customers. The wheel rotates counterclockwise, and each rotation costs you runningCost dollars. At each rotation, a new group of customers arrives, and each customer boards the gondola at a boardingCost price. You need to calculate the maximum profit after a certain number of rotations, considering both the cost and the revenue generated.

You can stop the wheel at any time, but continuing may either increase or decrease the total profit. The number of customers waiting at the wheel can exceed the gondola capacity of four, and only the first four customers can board at any given rotation. If no positive profit is possible after rotating through all customers, return -1.

Examples

Example 1

Input: customers = [8,3], boardingCost = 5, runningCost = 6

Output: 3

The numbers written on the gondolas are the number of people currently there.

8 customers arrive, 4 board and 4 wait for the next gondola, the wheel rotates. Current profit is 4 * $5 - 1 *$ 6 = $14.
3 customers arrive, the 4 waiting board the wheel and the other 3 wait, the wheel rotates. Current profit is 8 * $5 - 2 *$ 6 = $28.
The final 3 customers board the gondola, the wheel rotates. Current profit is 11 * $5 - 3 *$ 6 = $37. The highest profit was$ 37 after rotating the wheel 3 times.

Example 2

Input: customers = [10,9,6], boardingCost = 6, runningCost = 4

Output: 7

10 customers arrive, 4 board and 6 wait for the next gondola, the wheel rotates. Current profit is 4 * $6 - 1 *$ 4 = $20.
9 customers arrive, 4 board and 11 wait (2 originally waiting, 9 newly waiting), the wheel rotates. Current profit is 8 * $6 - 2 *$ 4 = $40.
The final 6 customers arrive, 4 board and 13 wait, the wheel rotates. Current profit is 12 * $6 - 3 *$ 4 = $60.
4 board and 9 wait, the wheel rotates. Current profit is 16 * $6 - 4 *$ 4 = $80.
4 board and 5 wait, the wheel rotates. Current profit is 20 * $6 - 5 *$ 4 = $100.
4 board and 1 waits, the wheel rotates. Current profit is 24 * $6 - 6 *$ 4 = $120.
1 boards, the wheel rotates. Current profit is 25 * $6 - 7 *$ 4 = $122. The highest profit was$ 122 after rotating the wheel 7 times.

Example 3

Input: customers = [3,4,0,5,1], boardingCost = 1, runningCost = 92

Output: -1

3 customers arrive, 3 board and 0 wait, the wheel rotates. Current profit is 3 * $1 - 1 *$ 92 = -$89.
4 customers arrive, 4 board and 0 wait, the wheel rotates. Current profit is 7 * $1 - 2 *$ 92 = -$177.
0 customers arrive, 0 board and 0 wait, the wheel rotates. Current profit is 7 * $1 - 3 *$ 92 = -$269.
5 customers arrive, 4 board and 1 waits, the wheel rotates. Current profit is 11 * $1 - 4 *$ 92 = -$357.
1 customer arrives, 2 board and 0 wait, the wheel rotates. Current profit is 13 * $1 - 5 *$ 92 = -$447. The profit was never positive, so return -1.

Constraints

n == customers.length
1 <= n <= 105
0 <= customers[i] <= 50
1 <= boardingCost, runningCost <= 100

Solution Approach

Simulate the Process

Simulate each rotation by tracking the number of customers boarding, calculating profit after each rotation, and adjusting for the gondola's capacity. This simulation approach captures the dynamic change in profit as customers board the gondolas.

Track Profit Calculation

For each rotation, calculate profit as revenue (boardingCost * number of customers boarded) minus the cost of running the wheel (runningCost). Keep track of the highest profit encountered during the simulation.

Determine Optimal Stopping Point

Monitor whether continuing to the next rotation is profitable. If profit after the next rotation is less than the current maximum, stop and return the highest profit.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) because the solution iterates through each customer arrival once. The space complexity is O(1) as only a few variables are needed for tracking the current state of the simulation.

What Interviewers Usually Probe

Candidate understands how to simulate the boarding process and calculate profits.
The candidate demonstrates the ability to handle dynamic adjustments in customer flow and gondola capacity.
The candidate successfully identifies the optimal stopping point to maximize profit.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the calculation of profit by not directly tracking revenue and cost per rotation.
Failing to consider the gondola capacity limit when customers exceed the number waiting to board.
Not accounting for the scenario where no positive profit can be made, and returning -1.

Follow-up variants

Modify the problem by introducing different gondola capacities for different rotations.
Add a restriction that requires a certain number of customers to always board the wheel, regardless of the gondola space.
Simulate the problem under different customer behavior models, such as customers leaving after a certain number of rotations.

FAQ

How does simulation apply to the Maximum Profit of Operating a Centennial Wheel problem?

Simulation is used to track customer arrivals, boarding, and profit after each rotation, making it essential to calculating the highest possible profit.

What’s the key challenge when solving the Maximum Profit of Operating a Centennial Wheel problem?

The challenge lies in determining the optimal stopping point and balancing customer arrivals with gondola capacity to maximize profit.

How do you handle multiple customers waiting to board the gondola in this problem?

Only four customers can board at each rotation, so the remaining customers must wait for the next rotation, which impacts profit calculations.

What happens if the profit is always negative in the Centennial Wheel problem?

If the profit remains negative after all rotations, the correct return value is -1, indicating no positive profit could be achieved.

Can the Maximum Profit of Operating a Centennial Wheel problem be optimized further?

While the current approach is efficient, further optimizations might include reducing unnecessary calculations or exploring alternative boarding strategies.

terminal

Solution

Solution 1: Simulation

We directly simulate the rotation process of the Ferris wheel. Each time it rotates, we add up the waiting customers and the newly arrived customers, then at most $4$ people get on the ride, update the number of waiting customers and profit, and record the maximum profit and its corresponding number of rotations.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def minOperationsMaxProfit(
        self, customers: List[int], boardingCost: int, runningCost: int
    ) -> int:
        ans = -1
        mx = t = 0
        wait = 0
        i = 0
        while wait or i < len(customers):
            wait += customers[i] if i < len(customers) else 0
            up = wait if wait < 4 else 4
            wait -= up
            t += up * boardingCost - runningCost
            i += 1
            if t > mx:
                mx = t
                ans = i
        return ans

Continue Practicing

#1583 count unhappy friends #1562 find latest group of size m #1560 most visited sector in a circular track