Leetcode 1599: Maximum Profit of Operating a Centennial Wheel
You operate a giant Ferris wheel with four gondolas, each holding up to four passengers. The Ferris wheel rotates counterclockwise and incurs a running cost for every rotation. You are given a list of customer arrivals, where each entry indicates the number of customers arriving just before the ith rotation. Customers board the gondola closest to the ground, and only a maximum of four customers can board at any time, while any excess wait for the next rotation. Each customer pays a boarding cost. Your task is to determine the minimum number of rotations needed to achieve the maximum profit. If there is no scenario where the profit is positive, return -1.
Problem
Approach
Steps
Complexity
Input: An array of integers representing the number of customers arriving just before each rotation.
Example: [12, 4]
Constraints:
• 1 <= n <= 10^5
• 0 <= customers[i] <= 50
• 1 <= boardingCost, runningCost <= 100
Output: Return the minimum number of rotations to achieve the maximum profit. If no profit can be achieved, return -1.
Example: 3
Constraints:
• Return the minimum number of rotations to achieve the maximum profit.
• If no profit can be achieved, return -1.
Goal: Determine the minimum number of rotations to maximize profit.
Steps:
• Keep track of the number of waiting customers.
• For each rotation, add new customers and board the maximum number of customers (up to 4).
• Compute the profit after each rotation by subtracting the running cost from the boarding revenue.
• Stop when the profit is maximized and return the number of rotations required.
Goal: Ensure that the number of customers does not exceed the number of gondolas available. Running and boarding costs must be within the specified range.
Steps:
• n = length of the customers array
• 1 <= n <= 10^5
• 0 <= customers[i] <= 50
• 1 <= boardingCost, runningCost <= 100
Assumptions:
• At most four customers can board per rotation.
• The wheel rotates counterclockwise.
• Once the wheel stops, no additional rotations will be made.
• Input: customers = [12, 4], boardingCost = 8, runningCost = 5
• Explanation: After 3 rotations, the maximum profit of $84 is achieved. Thus, the answer is 3.
Approach: To maximize profit, simulate each rotation and calculate the boarding revenue and running cost. Track the maximum profit and the corresponding rotation count.
Observations:
• The wheel can hold a maximum of 4 customers at a time.
• The goal is to stop when profit is maximized, even if not all customers are served.
• Start with an initial profit of zero and simulate the wheel's rotations.
• Track waiting customers and board up to 4 at a time.
Steps:
• Initialize variables for profit, rotations, and waiting customers.
• Iterate through each rotation, calculate the profit, and update the maximum profit and corresponding rotation count.
• If the profit becomes negative, stop the wheel and return -1.
Empty Inputs:
• If no customers arrive, the answer is 0 as no rotation is needed.
Large Inputs:
• Handle large arrays efficiently with O(n) time complexity.
Special Values:
• When the profit is never positive, return -1.
Constraints:
• Make sure to handle all edge cases where the profit might be zero or negative.
int minOperationsMaxProfit(vector<int>& cust, int boardingCost, int runningCost) {
/*
4gondolas
couter clockwise
running cost
*/
int n = cust.size();
int wait = 0;
int profit = 0, rot = 0;
int mx = INT_MIN;
int idx = 0;
while(idx < n || wait > 0) {
wait += idx < n? cust[idx]:0;
// cout << wait << " ";
if(wait > 4) {
profit += 4 * boardingCost - runningCost;
wait -= 4;
} else if(wait > 0) {
profit += wait * boardingCost - runningCost;
wait = 0;
}
if(mx < profit) {
mx = profit;
rot = idx + 1;
}
idx++;
}
return mx <= 0? -1: rot;
}
1 : Function Definition
int minOperationsMaxProfit(vector<int>& cust, int boardingCost, int runningCost) {
This is the function signature. It defines a function 'minOperationsMaxProfit' that takes a vector of integers 'cust', representing the number of customers at each stop, along with 'boardingCost' and 'runningCost' integers to calculate the profit.
2 : Variable Initialization
int n = cust.size();
This line initializes 'n' with the size of the 'cust' vector, representing the total number of stops or iterations.
3 : Variable Initialization
int wait = 0;
The 'wait' variable is initialized to 0. It will track the number of customers waiting at each stop.
4 : Variable Initialization
int profit = 0, rot = 0;
These variables initialize the profit (set to 0 initially) and the rotation count (rot) to track the rotation with the highest profit.
5 : Variable Initialization
int mx = INT_MIN;
The variable 'mx' is initialized to the minimum possible integer value to track the maximum profit during the iterations.
6 : Variable Initialization
int idx = 0;
The 'idx' variable is initialized to 0 and is used to iterate through the 'cust' vector.
7 : Loop
while(idx < n || wait > 0) {
This 'while' loop continues as long as there are customers to process (either in 'cust' or in 'wait').
8 : Customer Processing
wait += idx < n? cust[idx]:0;
The number of customers at the current stop ('cust[idx]') is added to 'wait', unless there are no more stops left (when 'idx' is out of bounds).
9 : Profit Calculation
if(wait > 4) {
If there are more than 4 waiting customers, the gondola will board 4 customers, and the profit will be calculated for that batch.
10 : Profit Calculation
profit += 4 * boardingCost - runningCost;
The profit is updated by boarding 4 customers at the 'boardingCost' and subtracting the 'runningCost'.
11 : Wait Adjustment
wait -= 4;
The number of waiting customers is reduced by 4, as 4 customers have boarded the gondola.
12 : Profit Calculation
} else if(wait > 0) {
If there are still some customers waiting but fewer than 4, the remaining customers board the gondola.
13 : Profit Calculation
profit += wait * boardingCost - runningCost;
The profit is updated based on the remaining number of waiting customers, charging the 'boardingCost' and subtracting the 'runningCost'.
14 : Wait Adjustment
wait = 0;
All waiting customers are boarded, so 'wait' is reset to 0.
15 : Profit Check
if(mx < profit) {
This checks if the current profit is greater than the previous maximum profit. If so, it updates 'mx' and tracks the rotation.
16 : Profit Update
mx = profit;
Updates the maximum profit ('mx') with the current profit.
17 : Rotation Update
rot = idx + 1;
Updates the rotation index 'rot' with the current gondola rotation.
18 : End Condition
}
This closes the 'if' block that checks if the current profit is the maximum.
19 : Index Update
idx++;
Increments the 'idx' to move to the next stop.
20 : Loop End
}
This ends the 'while' loop.
21 : Return
return mx <= 0? -1: rot;
If the maximum profit ('mx') is less than or equal to 0, it returns -1 (no profit). Otherwise, it returns the optimal rotation number ('rot').
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear, as we iterate through the customers array once.
Best Case: O(1)
Worst Case: O(1)
Description: We use only a constant amount of extra space.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus