LeetCode Solutions Blog

Status of Flight Tickets

Number: 3003

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

Given two tables, Flights and Passengers, where each flight has a fixed capacity and passengers book tickets with a specific booking_time, determine whether each passenger’s ticket is confirmed or waitlisted. A ticket is confirmed if the number of bookings made before (or at the same time as) the current booking (when ordered by booking_time) is within the flight’s capacity. Otherwise, the ticket is marked as waitlisted. The final output should list passenger_id and ticket status (Confirmed/Waitlist) ordered by passenger_id in ascending order.

Key Insights

For each flight, sort the associated passengers by their booking_time.
The first "capacity" number of bookings on each flight get confirmed.
Bookings beyond the flight's capacity are marked as waitlist.
The final result must be sorted by passenger_id in ascending order.
A join between Flights and Passengers (or keyed mapping in code) is required by flight_id.

Space and Time Complexity

Time Complexity: O(P log P) where P is the number of passengers (sorting the passengers per flight can contribute to the log factor).
Space Complexity: O(P + F) where P is the number of passengers and F is the number of flights.

Solution

The solution involves the following steps:

Map each flight_id to its capacity.
Group all passengers by flight_id and sort these groups by booking_time.
For each flight group, iterate over the sorted passengers:
- Mark the first "capacity" passengers as Confirmed.
- Mark the rest as Waitlist.
Store the results in a dictionary (or list) and finally output the results sorted by passenger_id.

Data structures used:

Dictionary (hash map) to map flight_id to capacity.
Dictionary to map flight_id to list of passengers.
Sorting for ordering passengers by booking_time within each flight.

This algorithm ensures that we process each passenger only once (after grouping) and the result is then assembled in the required order.

Code Solutions

# Python solution
from datetime import datetime

def ticket_status(flights, passengers):
    # Create a map from flight_id to capacity
    flight_capacity = {flight['flight_id']: flight['capacity'] for flight in flights}
    
    # Group passengers by flight_id
    flight_passengers = {}
    for passenger in passengers:
        flight_id = passenger['flight_id']
        if flight_id not in flight_passengers:
            flight_passengers[flight_id] = []
        flight_passengers[flight_id].append(passenger)
        
    # For each flight, sort the passengers by booking_time
    status_map = {}
    for flight_id, plist in flight_passengers.items():
        # Sort by booking_time (assume ISO format for datetime strings)
        sorted_list = sorted(plist, key=lambda p: datetime.strptime(p['booking_time'], "%Y-%m-%d %H:%M:%S"))
        capacity = flight_capacity[flight_id]
        # Mark booking status based on position (index)
        for index, p in enumerate(sorted_list):
            if index < capacity:
                status_map[p['passenger_id']] = 'Confirmed'
            else:
                status_map[p['passenger_id']] = 'Waitlist'
    
    # Prepare the result sorted by passenger_id in ascending order
    result = []
    for pid in sorted(status_map.keys()):
        result.append({"passenger_id": pid, "Status": status_map[pid]})
    return result

# Example usage:
flights = [
    {"flight_id": 1, "capacity": 2},
    {"flight_id": 2, "capacity": 2},
    {"flight_id": 3, "capacity": 1}
]
passengers = [
    {"passenger_id": 101, "flight_id": 1, "booking_time": "2023-07-10 16:30:00"},
    {"passenger_id": 102, "flight_id": 1, "booking_time": "2023-07-10 17:45:00"},
    {"passenger_id": 103, "flight_id": 1, "booking_time": "2023-07-10 12:00:00"},
    {"passenger_id": 104, "flight_id": 2, "booking_time": "2023-07-05 13:23:00"},
    {"passenger_id": 105, "flight_id": 2, "booking_time": "2023-07-05 09:00:00"},
    {"passenger_id": 106, "flight_id": 3, "booking_time": "2023-07-08 11:10:00"},
    {"passenger_id": 107, "flight_id": 3, "booking_time": "2023-07-08 09:10:00"}
]

result = ticket_status(flights, passengers)
print(result)  # Expected output in ascending order of passenger_id