1599. Maximum Profit of Operating a Centennial Wheel
Problem Description
You're in charge of a Ferris wheel (the Centennial Wheel) that has four gondolas, and each gondola can hold up to four people. You can rotate the wheel counterclockwise to bring one gondola down to the ground to let people on and off, but each rotation costs some amount of money (runningCost
). There are n
groups of customers, represented by an array customers
, where customers[i]
indicates how many new customers are ready to board the Ferris wheel just before the i
th rotation. You must rotate the wheel to serve these customers, but no new customer should wait if there's room available on the gondola. The customers also pay you a certain amount (boardingCost
) every time they board the gondola. Your goal is to figure out the minimum number of rotations you need to perform to maximize your profit from operating the Ferris wheel. If you cannot make a profit, the answer should be -1
.
Intuition
To solve the problem, we need to consider the cost of running a rotation against the revenue from boarding customers. We calculate profit incrementally with each customer and each rotation, taking into account the existing customers waiting to board. The profit at any step is the total money earned from boarding passengers minus the total cost of rotations so far.
We continue rotating the wheel, serving customers, and updating the total profit until there are no customers waiting or no more groups arriving. We also keep track of the maximum profit encountered and the number of rotations it took to reach that profit.
To arrive at the solution, we need to maintain a few variables as we process each group of customers: the current waiting number of customers (wait
), the total profit (t
), and the current rotation index (i
). For each group, we serve up to 4 customers (or fewer if we have fewer waiting). We then calculate the profit and update the maximum profit (mx
) if the current profit exceeds it. We remember the rotation at which the maximum profit was achieved (ans
).
After processing all customers, we return the rotation count when the maximum profit was achieved. If there was never a positive profit, we return -1
.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Solution Approach
The implementation of the solution is quite straightforward and iterative. It hinges on a loop that simulates the operation of the wheel, serving customers group by group and calculating profits.
- We initiate a while loop that continues as long as there are waiting customers (
wait
) or there are still groups of customers we haven't processed (controlled by checking if indexi
is less than the length ofcustomers
). - On each iteration, if the index
i
is within bounds of the array, we add the number of new customers arriving (customers[i]
) to the number of waiting customers (wait
). - We simulate boarding customers onto the gondola by taking the smaller of the number of waiting customers (
wait
) or the maximum capacity of a gondola (4
). This number is stored in the variableup
. - We then subtract the number of customers who have boarded from the waiting queue (
wait
). - The total profit (
t
) is updated by adding the revenue from boarding customers (up * boardingCost
) and subtracting the running cost (runningCost
). - The rotation counter (
i
) is incremented as we have completed a rotation. - If the total profit after this rotation exceeds the maximum recorded profit (
mx
), we updatemx
and also record the number of rotations it took to reach this new maximum profit withans = i
. - Lastly, after the loop finishes executing, we return the
ans
. Ifmx
(maximum profit) has never been positive, thenans
would still be-1
, indicating no profitable scenario was encountered.
Variables used:
wait
: an integer to keep track of the number of waiting customers.up
: an integer representing the number of customers that board the wheel in each rotation.t
: an integer to keep the running total of profit.mx
: an integer to store the maximum profit achieved at any point.ans
: an integer to store the number of rotations at whichmx
was achieved.i
: an integer used as an index to iterate over the array of customers and also to count the number of rotations.
Algo/Pattern used:
- The pattern used here is a simple iteration over the customer's array and updating states(
wait
,t
,mx
,ans
) based on the customers served and the cost incurred in each rotation. - The algorithm continuously compares the running profit with the maximum observed profit to identify the optimal stopping point.
- The loop ensures that all customers are served if profitable by not terminating until
wait
is empty, meaning no customers are left waiting.
This approach requires no complex data structures and is efficient, with a time complexity of O(n)
where n
is the number of customer groups, because it passes through the customer list only once.
What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?
Example Walkthrough
Let's consider an example where the runningCost
is 5
, the boardingCost
is 6
, and we have customers
array [8, 1]
.
Following the solution approach:
- Initially, we set
wait = 0
,t = 0
,mx = -1
,ans = -1
, andi = 0
. - In the first rotation (i = 0), we start with
customers[0] = 8
. Thewait
gets updated to8
. Since the capacity of a gondola is4
,up = min(wait, 4) = 4
. - Now,
4
customers board, sowait
becomes8-4 = 4
. We calculate profit byt = t + (up * boardingCost) - runningCost
which becomes0 + (4 * 6) - 5 = 19
. Since19 > mx
, we updatemx = 19
andans = i + 1 = 1
. - Rotation i is incremented,
i = 1
. - In the second rotation (i = 1), the
customers[1] = 1
is added towait
, so thewait
becomes4 + 1 = 5
. Again,up = min(wait, 4) = 4
. 4
customers board, sowait
becomes5 - 4 = 1
. Update the profit:t = 19 + (4 * 6) - 5 = 38
. Now38 > mx
, so we updatemx = 38
andans = i + 1 = 2
.- Increase rotation index,
i = 2
. - In the third rotation (i = 2), there are no more customers in the array, but we still have
1
customer waiting.up = min(wait, 4) = 1
. 1
customer boards,wait
becomes1 - 1 = 0
. Update the profit:t = 38 + (1 * 6) - 5 = 39
. The profitmx
remains unchanged as39
is not greater than38
, so no updates tomx
orans
.- Since there are no more customers waiting or in the array, we stop.
At the end of these rotations, the maximum profit mx
was 38
, which occurred after 2
rotations. Hence, the answer is ans = 2
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def min_operations_max_profit(self, customers: List[int], boarding_cost: int, running_cost: int) -> int:
5 # Initialize necessary variables
6 max_profit = total_profit = 0
7 waiting_customers = 0
8 rotations = 0
9 best_rotation = -1 # Set to -1 as default when no solution is found
10
11 # Iterate over the customers list and continue as long as there are waiting customers or unprocessed days
12 while waiting_customers > 0 or rotations < len(customers):
13 # Add customers from the current day if it exists
14 if rotations < len(customers):
15 waiting_customers += customers[rotations]
16
17 # Calculate the number of customers that can board (up to 4)
18 boarding_customers = min(waiting_customers, 4)
19 waiting_customers -= boarding_customers
20
21 # Update total profit
22 total_profit += boarding_customers * boarding_cost - running_cost
23
24 # Check and store the maximum profit and corresponding rotation
25 if total_profit > max_profit:
26 max_profit = total_profit
27 best_rotation = rotations + 1 # Add 1 for the 1-indexed result
28
29 # Move to the next rotation
30 rotations += 1
31
32 # Return the best rotation for maximum profit or -1 if no profit is ever reached
33 return best_rotation
34
1class Solution {
2
3 public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
4 // Initialize variables to store:
5 // 'maxProfit': the current maximum profit seen (initialized to 0).
6 // 'totalOperations': the total number of operations to achieve the 'maxProfit'.
7 // 'waitingCustomers': the number of customers waiting to board.
8 // 'currentRotation': the current rotation/round of the gondola.
9 int maxProfit = 0;
10 int totalOperations = -1; // Begins at -1 to handle cases when no profit can be made.
11 int waitingCustomers = 0;
12 int currentRotation = 0;
13
14 // Loop through all the customers or until there are no more waiting customers.
15 while (waitingCustomers > 0 || currentRotation < customers.length) {
16 // Add the customers arriving in the current rotation to 'waitingCustomers'.
17 if (currentRotation < customers.length) {
18 waitingCustomers += customers[currentRotation];
19 }
20
21 // Calculate the number of people to board in this rotation.
22 // It should not exceed 4, which is the gondola's capacity.
23 int boardingCustomers = Math.min(4, waitingCustomers);
24
25 // Decrease the count of 'waitingCustomers' by the number of people who just boarded.
26 waitingCustomers -= boardingCustomers;
27
28 // Move to the next rotation.
29 currentRotation++;
30
31 // Calculate the total profit after this rotation.
32 int profitThisRotation = boardingCustomers * boardingCost - runningCost;
33
34 // Add the profit from this rotation to the total profit.
35 maxProfit += profitThisRotation;
36
37 // Check if the total profit we just calculated is greater than the previously recorded maximum profit.
38 // If it is, update the 'maxProfit' and 'totalOperations'.
39 if (maxProfit > 0 && maxProfit > maxProfit) {
40 maxProfit = maxProfit;
41 totalOperations = currentRotation;
42 }
43 }
44
45 // Return the total number of operations needed to reach maximum profit.
46 // If a profit cannot be made, 'totalOperations' would be -1.
47 return totalOperations;
48 }
49}
50
1#include <vector> // Include necessary library for vector usage
2#include <algorithm> // Include necessary library for using min function
3
4class Solution {
5public:
6 int minOperationsMaxProfit(std::vector<int>& customers, int boardingCost, int runningCost) {
7 int maxProfit = -1; // Initialize variable to store the maximum profit index
8 int currentProfit = 0; // Current profit initialized to zero
9 int totalWaitingCustomers = 0; // Counter for customers waiting
10 int rotations = 0; // Counter for the number of rotations
11 int currentlyBoarded; // Customers that can board the ride on current rotation
12
13 // Loop until we've processed all customers or until there are no more waiting customers
14 while (totalWaitingCustomers > 0 || rotations < customers.size()) {
15 // Add customers from the current rotation if it exists
16 if (rotations < customers.size()) {
17 totalWaitingCustomers += customers[rotations];
18 }
19
20 // Board up to 4 customers or the number of waiting customers, whichever is lower
21 currentlyBoarded = std::min(4, totalWaitingCustomers);
22 // Subtract the boarded customers from the waiting queue
23 totalWaitingCustomers -= currentlyBoarded;
24 // Move to the next rotation
25 rotations++;
26
27 // Update the current profit by adding profit from boarding customers and subtracting the running cost
28 currentProfit += currentlyBoarded * boardingCost - runningCost;
29
30 // If the current profit is greater than the max profit, update maxProfit and store the current rotation
31 if (currentProfit > maxProfit) {
32 maxProfit = currentProfit;
33 maxProfit = rotations; // Store the most profitable rotation
34 }
35 }
36
37 // If maxProfit remains -1, it means that running the ride was never profitable; otherwise, return the number of rotations
38 return (maxProfit > 0 ? maxProfit : -1);
39 }
40};
41
1import { min } from "lodash"; // Assuming lodash is used for the `min` function, otherwise native Math.min can be used.
2
3// This variable holds the maximum profit calculated, initialized with -1 indicating no profit has been made.
4let maxProfit: number = -1;
5
6// Function to calculate number of operations needed to reach maximum profit from the given boarding and running costs.
7// Takes in an array of customers, boarding cost per person, and running cost per ride.
8function minOperationsMaxProfit(customers: number[], boardingCost: number, runningCost: number): number {
9 // Stores the current profit made, initialized to 0.
10 let currentProfit: number = 0;
11 // Counts the total number of customers waiting in line.
12 let totalWaitingCustomers: number = 0;
13 // Counts how many rotations the ride has been through.
14 let rotations: number = 0;
15 // Number of customers that can board the ride in the current rotation.
16 let currentlyBoarded: number;
17
18 // Continue looping until all customers are processed or there are no more waiting customers.
19 while (totalWaitingCustomers > 0 || rotations < customers.length) {
20 // If there are remaining rotations, add customers to the waiting total.
21 if (rotations < customers.length) {
22 totalWaitingCustomers += customers[rotations];
23 }
24
25 // Board the number of customers that is the lesser of available seats (4) or waiting customers.
26 currentlyBoarded = min([4, totalWaitingCustomers])!;
27 // Reduce the number of total waiting customers by the amount that just boarded the ride.
28 totalWaitingCustomers -= currentlyBoarded;
29 // Increment rotation count, moving to the next cycle.
30 rotations++;
31
32 // Update the running total of current profit by adding profit from customers times the boarding
33 // cost and subtracting the cost of running the ride.
34 currentProfit += currentlyBoarded * boardingCost - runningCost;
35
36 // If current profit is greater than what's recorded in maxProfit, update maxProfit to
37 // the newest profit and set the count of rotations at which max profit occurred.
38 if (currentProfit > maxProfit) {
39 maxProfit = currentProfit; // Update the max profit to the new profit.
40 maxProfit = rotations; // This should actually store the rotation count, needs correction.
41 }
42 }
43
44 // If maxProfit is still -1, it means running the ride never turned profitable.
45 // Otherwise, return the optimized number of rotations to reach max profit.
46 return (maxProfit > 0 ? maxProfit : -1);
47}
48
Which two pointer techniques do you use to check if a string is a palindrome?
Time and Space Complexity
Time Complexity
The time complexity of the code is O(n)
, where n
is the number of elements in the customers
list. This is because the loop runs for each customer in the customers
list plus additional iterations for any remaining waiting customers after the end of the list. The operations inside the loop are constant time, which means they do not depend on the size of the input list, so the time complexity is linear with regard to the number of elements in the input.
Space Complexity
The space complexity of the code is O(1)
. The function uses a fixed number of variables (ans
, mx
, t
, wait
, i
, and up
) whose space requirement does not scale with the input size (the number of customers). Hence, the space used by the algorithm is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
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.