Problem

Table: Flights

1
2
3
4
5
6
7
8

+-------------+------+
| Column Name | Type |
+-------------+------+
| flight_id   | int  |
| capacity    | int  |
+-------------+------+
flight_id column contains distinct values.
Each row of this table contains flight id and capacity.

Table: Passengers

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

+--------------+----------+
| Column Name  | Type     |
+--------------+----------+
| passenger_id | int      |
| flight_id    | int      |
| booking_time | datetime |
+--------------+----------+
passenger_id column contains distinct values.
booking_time column contains distinct values.
Each row of this table contains passenger id, booking time, and their flight id.

Passengers book tickets for flights in advance. If a passenger books a ticket for a flight and there are still empty seats available on the flight, the passenger’s ticket will be confirmed. However, the passenger will be on a waitlist if the flight is already at full capacity.

Write a solution to determine the current status of flight tickets for each passenger.

Return the result table ordered by passenger_id inascending order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

Input: 
Flights table:
+-----------+----------+
| flight_id | capacity |
+-----------+----------+
| 1         | 2        |
| 2         | 2        |
| 3         | 1        |
+-----------+----------+
Passengers table:
+--------------+-----------+---------------------+
| passenger_id | flight_id | booking_time        |
+--------------+-----------+---------------------+
| 101          | 1         | 2023-07-10 16:30:00 |
| 102          | 1         | 2023-07-10 17:45:00 |
| 103          | 1         | 2023-07-10 12:00:00 |
| 104          | 2         | 2023-07-05 13:23:00 |
| 105          | 2         | 2023-07-05 09:00:00 |
| 106          | 3         | 2023-07-08 11:10:00 |
| 107          | 3         | 2023-07-08 09:10:00 |
+--------------+-----------+---------------------+
Output: 
+--------------+-----------+
| passenger_id | Status    |
+--------------+-----------+
| 101          | Confirmed | 
| 102          | Waitlist  | 
| 103          | Confirmed | 
| 104          | Confirmed | 
| 105          | Confirmed | 
| 106          | Waitlist  | 
| 107          | Confirmed | 
+--------------+-----------+
Explanation: 
- Flight 1 has a capacity of 2 passengers. Passenger 101 and Passenger 103 were the first to book tickets, securing the available seats. Therefore, their bookings are confirmed. However, Passenger 102 was the third person to book a ticket for this flight, which means there are no more available seats. Passenger 102 is now placed on the waitlist, 
- Flight 2 has a capacity of 2 passengers, Flight 2 has exactly two passengers who booked tickets,  Passenger 104 and Passenger 105. Since the number of passengers who booked tickets matches the available seats, both bookings are confirmed.
- Flight 3 has a capacity of 1 passenger. Passenger 107 booked earlier and secured the only available seat, confirming their booking. Passenger 106, who booked after Passenger 107, is on the waitlist.

Solution

Method 1 – Window Function and Sorting

Intuition

We need to determine for each passenger if their booking is “Confirmed” or “Waitlist” based on the order they booked and the flight’s capacity. The key idea is to rank bookings for each flight by booking time and compare the rank to the flight’s capacity.

Approach

  1. For each passenger, assign a rank based on their booking time within their flight (earliest booking gets rank 1).
  2. Join the passenger data with flight capacity.
  3. If a passenger’s rank is less than or equal to the flight’s capacity, their booking is “Confirmed”; otherwise, it’s “Waitlist”.
  4. Return the result ordered by passenger_id ascending.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

SELECT
  p.passenger_id,
  CASE
    WHEN rn <= f.capacity THEN 'Confirmed'
    ELSE 'Waitlist'
  END AS Status
FROM (
  SELECT
    passenger_id,
    flight_id,
    booking_time,
    ROW_NUMBER() OVER (PARTITION BY flight_id ORDER BY booking_time) AS rn
  FROM Passengers
) p
JOIN Flights f ON p.flight_id = f.flight_id
ORDER BY p.passenger_id;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

SELECT
  p.passenger_id,
  CASE
    WHEN rn <= f.capacity THEN 'Confirmed'
    ELSE 'Waitlist'
  END AS Status
FROM (
  SELECT
    passenger_id,
    flight_id,
    booking_time,
    ROW_NUMBER() OVER (PARTITION BY flight_id ORDER BY booking_time) AS rn
  FROM Passengers
) p
JOIN Flights f ON p.flight_id = f.flight_id
ORDER BY p.passenger_id;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def status_of_flight_tickets(
        self,
        flights: 'pd.DataFrame',
        passengers: 'pd.DataFrame'
    ) -> 'pd.DataFrame':
        df = passengers.copy()
        df = df.sort_values(['flight_id', 'booking_time'])
        df['rn'] = df.groupby('flight_id').cumcount() + 1
        df = df.merge(flights, on='flight_id')
        df['Status'] = df.apply(
            lambda x: 'Confirmed' if x['rn'] <= x['capacity'] else 'Waitlist',
            axis=1
        )
        ans = df[['passenger_id', 'Status']].sort_values('passenger_id').reset_index(drop=True)
        return ans

Complexity

  • ⏰ Time complexity: O(n log n) – Sorting passengers by flight and booking time dominates, plus window function/grouping.
  • 🧺 Space complexity: O(n) – Extra columns for rank and status, plus join/merge operations.