Airplane Seat Assignment Probability - Leetcode Solution

Problem Statement:

There are n seats and n passengers in a plane. The seats are arranged in n rows and are numbered from 1 to n.

The passengers arrive one by one according to their IDs and take the seats. The seat ID is equal to the passenger ID.

If the seat is already occupied, the passenger will be assigned to the next available seat in the following order:

• The passenger first looks for the seat that is unoccupied and closest to their original seat.
• If there is no unoccupied seat available, they will take the last unoccupied seat in the order of seat ID.

Return the probability that each passenger can get their own seat.

Solution:

First, let's consider the case when there are only two seats.

If the first passenger takes their own seat, the second passenger will take their own seat too. Hence, the probability is 1/2.

If the first passenger takes the second passenger's seat, the second passenger will take the first passenger's seat with probability 1/2, and their own seat with probability 1/2. Hence, the probability is also 1/2.

So the probability of each passenger getting their own seat when there are only two seats is 1/2.

Now let's consider the case when there are more than two seats.

Suppose the first passenger takes the i-th seat (1 < i < n), then the passengers with IDs (i+1), (i+2), ..., n will take their own seats since their seats are still unoccupied.

The passenger with ID i+1 will take the i-th seat with probability 1/2, and their own seat with probability 1/2. If they take their own seat, then the passengers with IDs (i+2), (i+3), ..., n will also take their own seats. If they take the i-th seat, then the same process repeats with the passenger with ID i+2.

Therefore, the probability of each passenger getting their own seat is:

• If the first passenger takes their own seat, the probability is 1/n.
• If the first passenger takes the i-th seat (1 < i < n), the probability is 1/2 * (1/n + the probability that the passenger with ID i+1 gets their own seat).

We can use dynamic programming to calculate the probability that each passenger gets their own seat. Let P(i) denote the probability that the i-th passenger gets their own seat. Then we have:

• P(n) = 1, since the last passenger will always get their own seat.
• P(n-1) = 1/2, since the last passenger will always take their own seat if it's available.
• P(i) = 1/n + 1/2 * (P(i+1) + P(i+2) + ... + P(n)), if 1 < i < n.

The last equation can be calculated recursively from P(n-1) to P(1).

The time complexity of the algorithm is O(n^2) and the space complexity is O(n).

1