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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.