Solution

Method 1 – Simulation with Greedy Boarding

Intuition

We simulate the process of rotating the wheel, always boarding as many customers as possible (up to 4 per rotation). We keep track of the profit after each rotation and record the rotation with the highest profit.

Approach

Initialize variables for waiting customers, total boarded, current profit, max profit, and the answer (rotation count).
For each rotation (while there are customers to process or waiting customers):
- Add new arrivals to the waiting queue.
- Board up to 4 customers.
- Update total boarded and waiting.
- Calculate profit: total boarded * boardingCost - rotations * runningCost.
- If profit exceeds max profit, update max profit and record the rotation.
Return the rotation count with max profit, or -1 if profit never positive.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int minOperationsMaxProfit(vector<int>& customers, int boardingCost, int runningCost) {\n        int wait = 0, total = 0, ans = -1, maxProfit = 0, profit = 0, rot = 0, i = 0;\n        while (wait > 0 || i < customers.size()) {\n            if (i < customers.size()) wait += customers[i++];\n            int board = min(4, wait);\n            wait -= board;\n            total += board;\n            rot++;\n            profit = total * boardingCost - rot * runningCost;\n            if (profit > maxProfit) {\n                maxProfit = profit;\n                ans = rot;\n            }\n        }\n        return maxProfit > 0 ? ans : -1;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> minOperationsMaxProfit</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></sp

Related Tags