We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Profit of Operating a Centennial Wheel

Number: 1721

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

You are operating a Centennial Wheel with four gondolas where each gondola can hold up to four people. Customers arrive in batches given by an array, and you can only load up to four at a time. Each rotation incurs a runningCost while each boarded customer earns a boardingCost. You want to determine the minimum number of rotations required to maximize profit. If no positive profit scenario exists, return -1.

Key Insights

  • Simulate the wheel rotations while tracking waiting customers.
  • At each rotation, add the new arriving customers (if any) before boarding.
  • Board at most four customers per rotation and update running cost and profit.
  • After processing all arrivals, continue rotations until no customers remain waiting.
  • Maintain and update the maximum profit and the corresponding rotation count.
  • If the computed maximum profit is not positive, return -1.

Space and Time Complexity

Time Complexity: O(n + k), where n is the number of customer arrival events and k is the number of extra rotations needed after processing the customers.
Space Complexity: O(1)

Solution

We use a simulation approach. For each rotation, first add any new arriving customers to the waiting queue, then board up to four customers. Update the total profit by considering the boarding revenue and the running cost for that rotation. Always keep track of the maximum profit seen and the rotation count at which it occurs. After processing all customer arrivals, if there are still waiting customers, continue the simulation until all customers have boarded. In the end, return the rotation count of maximum profit if profit is positive; otherwise, return -1.

Code Solutions

# Python solution with line-by-line comments

def maxProfit(customers, boardingCost, runningCost):
    waiting = 0                 # Number of customers waiting to board
    totalProfit = 0             # Total profit accumulated so far
    maxProfit = 0               # Maximum profit observed
    bestRotation = -1           # Rotation count at which maximum profit occurs
    rotation = 0                # Current rotation count
    n = len(customers)          # Total number of customer arrival instances
    i = 0                       # Index to iterate through customers

    # Process rotations for each customer arrival event
    while i < n or waiting:
        if i < n:
            # Add arriving customers before current rotation
            waiting += customers[i]
            i += 1
        # Compute the number of customers boarding in this rotation
        boarded = min(4, waiting)
        waiting -= boarded
        
        # Update profit for this rotation: boarding revenue - running cost
        totalProfit += boarded * boardingCost - runningCost
        rotation += 1   # Completed one rotation

        # Track the maximum profit and the rotation count associated with it
        if totalProfit > maxProfit:
            maxProfit = totalProfit
            bestRotation = rotation

    # Return bestRotation if profit is positive, else -1
    return bestRotation if maxProfit > 0 else -1

# Example usage:
#print(maxProfit([8,3], 5, 6))  # Expected output: 3
#print(maxProfit([10,9,6], 6, 4))  # Expected output: 7
#print(maxProfit([3,4,0,5,1], 1, 92))  # Expected output: -1
← Back to All Questions