231. Design Uber Shuttle Seats

Design Uber Shuttle Seats

There is an Uber Shuttle with n seats in one row, numbered from 0 to n - 1. Riders board one at a time. Each new rider chooses the empty seat that maximizes the distance to the nearest occupied seat. If multiple seats give the same distance, the rider chooses the seat with the smallest number. If the shuttle is empty, the rider sits at seat 0.

Design a class that simulates riders boarding and dropping off from the shuttle.

Class

Uber Shuttle

UberShuttle(int n)

Initializes an Uber Shuttle with n seats.
Initially, all seats are empty.

Methods

Board

int board()

Returns the seat number chosen by the next rider.
The returned seat becomes occupied.
The chosen seat must maximize the distance to the nearest occupied seat.
If there is a tie, return the smallest seat number.
If no rider is currently seated, return 0.

Drop Off

void dropOff(int p)

The rider sitting at seat p leaves the shuttle.
After this call, seat p becomes empty.

Constraints

1 ≤ n ≤ 1,000,000,000
0 ≤ p < n
board() is called only when at least one seat is empty.
dropOff(p) is called only when seat p is currently occupied.
For every tie during seat selection, the smaller seat number is chosen first.

Examples

Example 1

UberShuttle shuttle = new UberShuttle(n = 8)

shuttle.board() returns 0

shuttle.board() returns 7

shuttle.board() returns 3

shuttle.board() returns 5

Riders choose seats 0, 7, 3, and 5 because each selected seat gives the maximum possible distance from the nearest occupied seat.

Example 2

UberShuttle shuttle = new UberShuttle(n = 10)

shuttle.board() returns 0

shuttle.board() returns 9

shuttle.board() returns 4

shuttle.dropOff(p = 0)

shuttle.board() returns 0

After seat 0 becomes empty, it again gives the maximum distance among all empty seats, so the next rider takes seat 0.

Example 3

UberShuttle shuttle = new UberShuttle(n = 5)

shuttle.board() returns 0

shuttle.board() returns 4

shuttle.board() returns 2

shuttle.dropOff(p = 4)

shuttle.board() returns 4

Seat 4 is chosen again because it is farthest from the nearest occupied seat.