Problem

Table: Flights

+-------------+------+
| Column Name | Type |
+-------------+------+
| flight_id   | int  |
| capacity    | int  |
+-------------+------+
flight_id is the column with unique values for this table.
Each row of this table contains flight id and its capacity.

Table: Passengers

+--------------+------+
| Column Name  | Type |
+--------------+------+
| passenger_id | int  |
| flight_id    | int  |
+--------------+------+
passenger_id is the column with unique values for this table.
Each row of this table contains passenger id and 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 ticket will be confirmed. However, the passenger will be on a waitlist if the flight is already at full capacity.

Write a solution to report the number of passengers who successfully booked a flight (got a seat) and the number of passengers who are on the waitlist for each flight.

Return the result table ordered by __flight_id in ascending ** 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

Input: 
Flights table:
+-----------+----------+
| flight_id | capacity |
+-----------+----------+
| 1         | 2        |
| 2         | 2        |
| 3         | 1        |
+-----------+----------+
Passengers table:
+--------------+-----------+
| passenger_id | flight_id |
+--------------+-----------+
| 101          | 1         |
| 102          | 1         |
| 103          | 1         |
| 104          | 2         |
| 105          | 2         |
| 106          | 3         |
| 107          | 3         |
+--------------+-----------+
Output: 
+-----------+------------+--------------+
| flight_id | booked_cnt | waitlist_cnt |
+-----------+------------+--------------+
| 1         | 2          | 1            |
| 2         | 2          | 0            |
| 3         | 1          | 1            |
+-----------+------------+--------------+
Explanation: 
- Flight 1 has a capacity of 2. As there are 3 passengers who have booked tickets, only 2 passengers can get a seat. Therefore, 2 passengers are successfully booked, and 1 passenger is on the waitlist.
- Flight 2 has a capacity of 2. Since there are exactly 2 passengers who booked tickets, everyone can secure a seat. As a result, 2 passengers successfully booked their seats and there are no passengers on the waitlist.
- Flight 3 has a capacity of 1. As there are 2 passengers who have booked tickets, only 1 passenger can get a seat. Therefore, 1 passenger is successfully booked, and 1 passenger is on the waitlist.

Solution

Method 1 – Window Functions and Aggregation

Intuition

We need to count, for each flight, how many passengers got a seat (up to the flight’s capacity) and how many are on the waitlist (the rest). This can be done by ranking bookings per flight and comparing the rank to the capacity.

Approach

  1. For each flight, join with passengers to get all bookings.
  2. Use a window function (ROW_NUMBER) to assign a booking order for each passenger per flight.
  3. For each booking, if their booking order is less than or equal to the flight’s capacity, they are booked; otherwise, they are on the waitlist.
  4. Aggregate counts for booked and waitlisted passengers per flight.
  5. Include flights with zero bookings.
  6. Order the result by flight_id ascending.

Code

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

WITH ranked AS (
  SELECT f.flight_id, f.capacity, p.passenger_id,
         ROW_NUMBER() OVER (PARTITION BY f.flight_id ORDER BY p.passenger_id) AS rn
  FROM Flights f
  LEFT JOIN Passengers p ON f.flight_id = p.flight_id
)
SELECT
  r.flight_id,
  SUM(CASE WHEN r.rn <= r.capacity THEN 1 ELSE 0 END) AS booked_cnt,
  SUM(CASE WHEN r.rn > r.capacity THEN 1 ELSE 0 END) AS waitlist_cnt
FROM ranked r
GROUP BY r.flight_id
ORDER BY r.flight_id;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

WITH ranked AS (
  SELECT f.flight_id, f.capacity, p.passenger_id,
         ROW_NUMBER() OVER (PARTITION BY f.flight_id ORDER BY p.passenger_id) AS rn
  FROM Flights f
  LEFT JOIN Passengers p ON f.flight_id = p.flight_id
)
SELECT
  r.flight_id,
  SUM(CASE WHEN r.rn <= r.capacity THEN 1 ELSE 0 END) AS booked_cnt,
  SUM(CASE WHEN r.rn > r.capacity THEN 1 ELSE 0 END) AS waitlist_cnt
FROM ranked r
GROUP BY r.flight_id
ORDER BY r.flight_id;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def flight_occupancy(self, flights: 'pd.DataFrame', passengers: 'pd.DataFrame') -> 'pd.DataFrame':
        import pandas as pd
        df = flights.merge(passengers, on='flight_id', how='left')
        df['rn'] = df.groupby('flight_id').cumcount() + 1
        df['booked'] = df['rn'] <= df['capacity']
        df['waitlist'] = df['rn'] > df['capacity']
        agg = df.groupby('flight_id').agg(
            booked_cnt=('booked', 'sum'),
            waitlist_cnt=('waitlist', 'sum')
        ).reset_index()
        # Ensure all flights are present
        result = flights[['flight_id']].merge(agg, on='flight_id', how='left').fillna(0)
        result['booked_cnt'] = result['booked_cnt'].astype(int)
        result['waitlist_cnt'] = result['waitlist_cnt'].astype(int)
        return result.sort_values('flight_id').reset_index(drop=True)

Complexity

  • ⏰ Time complexity: O(n + m) where n is the number of passengers and m is the number of flights, since each booking and flight is processed once.
  • 🧺 Space complexity: O(n + m) for storing intermediate results and output.