Leetcode 1599. Maximum Profit of Operating a Centennial Wheel

Problem Explanation

You operate a ferris-wheel-like amusement ride known as the Centennial Wheel. This wheel has four gondolas, and each gondola can hold a maximum of four people. You can operate the wheel in a counterclockwise direction, which costs runningCost dollars each time, to allow people to board the gondola that has reached the ground.

Customers pay boardingCost dollars each for taking a ride and will exit when the gondola next comes down to the ground. New customers arrive just before each rotation, with the number of new arrivals given in the array customers[i], where i is the number of rotations so far.

You can choose to halt the wheel's operation at any time, but if there are more than four customers waiting when the wheel stops, you will have to operate the wheel further (free of cost) to get all the customers down safely.

The problem asks to determine the minimum number of rotations you need to perform to maximize your profit. If no profit is realizable i.e., the total cost of running the wheel exceeds the boarding cost paid by the customers, then return -1.

Solution Approach

The core idea of the solution is to continue operating the wheel until it becomes unprofitable to do so. We process the customer arrivals in order, insert new customers into a waiting queue, and then fill the gondolas with the waiting customers.

We then calculate the profit by subtracting the running cost from the product of the boarding cost and the number of customers that have boarded. If the profit is higher than the maximum profit recorded so far, we update it and record the number of rotations to reach that profit.

Once we have processed all customer arrivals and emptied the waiting queue, we return the minimum number of rotations needed to reach the maximum profit.

Python Solution

1
2python
3class Solution:
4    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:
5        waiting = 0
6        profit = 0
7        maxProfit = 0
8        rotate = 0
9        maxRotate = -1
10        i = 0
11
12        while waiting > 0 or i < len(customers):
13            if i < len(customers):
14                waiting += customers[i]
15                i += 1
16            newOnboard = min(waiting, 4)
17            waiting -= newOnboard
18            profit += newOnboard * boardingCost - runningCost
19            rotate += 1
20            if profit > maxProfit:
21                maxProfit = profit
22                maxRotate = rotate
23
24        return maxRotate

Java Solution

1
2java
3class Solution {
4    public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
5        int waiting = 0;
6        int profit = 0;
7        int maxProfit = 0;
8        int rotate = 0;
9        int maxRotate = -1;
10        int i = 0;
11
12        while (waiting > 0 || i < customers.length) {
13            if (i < customers.length) {
14                waiting += customers[i++];
15            }
16            int newOnboard = Math.min(waiting, 4);
17            waiting -= newOnboard;
18            profit += newOnboard * boardingCost - runningCost;
19            rotate++;
20            if (profit > maxProfit) {
21                maxProfit = profit;
22                maxRotate = rotate;
23            }
24        }
25
26        return maxRotate;
27    }
28}

JavaScript Solution

1
2javascript
3class Solution {
4    minOperationsMaxProfit(customers, boardingCost, runningCost) {
5        let waiting = 0;
6        let profit = 0;
7        let maxProfit = 0;
8        let rotate = 0;
9        let maxRotate = -1;
10        let i = 0;
11
12        while (waiting > 0 || i < customers.length) {
13            if (i < customers.length) {
14                waiting += customers[i++];
15            }
16            const newOnboard = Math.min(waiting, 4);
17            waiting -= newOnboard;
18            profit += newOnboard * boardingCost - runningCost;
19            rotate++;
20            if (profit > maxProfit) {
21                maxProfit = profit;
22                maxRotate = rotate;
23            }
24        }
25
26        return maxRotate;
27    }
28}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int minOperationsMaxProfit(vector<int>& customers, int boardingCost, int runningCost) {
6        int waiting = 0;
7        int profit = 0;
8        int maxProfit = 0;
9        int rotate = 0;
10        int maxRotate = -1;
11        int i = 0;
12
13        while (waiting > 0 || i < customers.size()) {
14            if (i < customers.size()) {
15                waiting += customers[i++];
16            }
17            int newOnboard = min(waiting, 4);
18            waiting -= newOnboard;
19            profit += newOnboard * boardingCost - runningCost;
20            rotate++;
21            if (profit > maxProfit) {
22                maxProfit = profit;
23                maxRotate = rotate;
24            }
25        }
26
27        return maxRotate;
28    }
29};

C# Solution

1
2csharp
3public class Solution {
4    public int MinOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
5        int waiting = 0;
6        int profit = 0;
7        int maxProfit = 0;
8        int rotate = 0;
9        int maxRotate = -1;
10        int i = 0;
11
12        while (waiting > 0 || i < customers.Length) {
13            if (i < customers.Length) {
14                waiting += customers[i++];
15        }
16        int newOnboard = Math.Min(waiting, 4);
17        waiting -= newOnboard;
18        profit += newOnboard * boardingCost - runningCost;
19        rotate++;
20        if (profit > maxProfit) {
21            maxProfit = profit;
22            maxRotate = rotate;
23        }
24
25        return maxRotate;
26    }
27}

Running These Solutions

In Python, you would call the function like this:

1
2python
3sol = Solution()
4print(sol.minOperationsMaxProfit([8,3], 5, 6)) # Returns 3

In Java, you would call the function like this:

1
2java
3Solution sol = new Solution();
4System.out.println(sol.minOperationsMaxProfit(new int[]{8,3}, 5, 6)); // Prints 3

In JavaScript, you would call the function like this:

1
2javascript
3const sol = new Solution();
4console.log(sol.minOperationsMaxProfit([8,3], 5, 6)); // Logs 3

In C++, the function can be called like this:

1
2cpp
3Solution sol;
4cout << sol.minOperationsMaxProfit({8,3}, 5, 6) << endl; // Prints 3

In C#, the function can be called like this:

1
2csharp
3Solution sol = new Solution();
4Console.WriteLine(sol.MinOperationsMaxProfit(new int[]{8,3}, 5, 6)); // Prints 3

Conclusion

In this problem, we learned to maximise the profit of operating a ferris wheel under given constraints. We solved this problem using a greedy approach where we keep rotating the wheel until it becomes unprofitable. We applied this approach in multiple programming languages. This required us to handle a queue of customers by filling the gondolas and then calculating the profit after each wheel rotation.