When to Stop the Ferris Wheel

Medium

You run a Ferris wheel. Riders board one car at ground level, and at most 4 people fit in it. Each spin of the wheel costs spin_cost, and each rider who boards pays ticket. Right before spin number i (0-based), arrivals[i] new visitors show up and join a shared queue. Before every spin, as many waiting people as fit (up to 4) board the car. The wheel keeps spinning after arrivals runs out, as long as anyone is still waiting. You may stop after any spin, even before everyone has ridden. The profit after k spins is the ticket money from those who boarded during them minus k · spin_cost; any spins needed afterwards to bring riders down are free. Return the smallest number of spins that gives the largest profit. If the profit is never positive, return -1.

Example 1

arrivals=[6, 1], ticket=3, spin_cost=4 → 2

Spin 1: 6 arrive, 4 board, profit 4 · 3 - 4 = 8. Spin 2: 1 arrives, the 2 still waiting and the newcomer board, 3 in total, profit 8 + 9 - 4 = 13. The queue is empty and further spins only lose money. The answer is 2.

Example 2

arrivals=[2, 2], ticket=1, spin_cost=5 → -1

Each spin brings in at most 2 · 1 = 2 and costs 5, so the profit is never positive and the answer is -1.

Example 3

arrivals=[0, 0, 9], ticket=10, spin_cost=7 → 5

Constraints

1 ≤ len(arrivals) ≤ 10⁵
0 ≤ arrivals[i] ≤ 50
1 ≤ ticket, spin_cost ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Simulation