1599. Maximum Profit of Operating a Centennial Wheel

MediumArraySimulation
Leetcode Link

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 ith 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.

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 index i is less than the length of customers).
  • 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 variable up.
  • 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 update mx and also record the number of rotations it took to reach this new maximum profit with ans = i.
  • Lastly, after the loop finishes executing, we return the ans. If mx (maximum profit) has never been positive, then ans 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 which mx 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.

💪
Level Up Your
Algo Skills

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:

  1. Initially, we set wait = 0, t = 0, mx = -1, ans = -1, and i = 0.
  2. In the first rotation (i = 0), we start with customers[0] = 8. The wait gets updated to 8. Since the capacity of a gondola is 4, up = min(wait, 4) = 4.
  3. Now, 4 customers board, so wait becomes 8-4 = 4. We calculate profit by t = t + (up * boardingCost) - runningCost which becomes 0 + (4 * 6) - 5 = 19. Since 19 > mx, we update mx = 19 and ans = i + 1 = 1.
  4. Rotation i is incremented, i = 1.
  5. In the second rotation (i = 1), the customers[1] = 1 is added to wait, so the wait becomes 4 + 1 = 5. Again, up = min(wait, 4) = 4.
  6. 4 customers board, so wait becomes 5 - 4 = 1. Update the profit: t = 19 + (4 * 6) - 5 = 38. Now 38 > mx, so we update mx = 38 and ans = i + 1 = 2.
  7. Increase rotation index, i = 2.
  8. 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.
  9. 1 customer boards, wait becomes 1 - 1 = 0. Update the profit: t = 38 + (1 * 6) - 5 = 39. The profit mx remains unchanged as 39 is not greater than 38, so no updates to mx or ans.
  10. 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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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

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.

😈
Become an
Algo Monster

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.


TA 👨‍🏫