We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Corporate Flight Bookings

Number: 1206

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Goldman Sachs

Problem Description

You are given a list of flight bookings where each booking reserves a fixed number of seats for a continuous range of flights. Given the total number of flights, the task is to calculate and return an array where each element represents the total number of seats reserved on that flight.

Key Insights

  • Use a difference array (or prefix sum technique) to handle range updates efficiently.
  • Instead of updating every flight in the given range for each booking (which could be too slow), update just the starting and ending points.
  • Accumulate the difference array to obtain the final bookings for each flight.

Space and Time Complexity

Time Complexity: O(n + m) where m is the number of bookings and n is the number of flights. Space Complexity: O(n) for storing the difference array and the final result.

Solution

The idea is to create an auxiliary array (or difference array) to optimize range updates. For each booking [start, end, seats]:

  • Add 'seats' to difference[start - 1] (adjusting for 0-based indexing).
  • Subtract 'seats' from difference[end], if end is less than n. This marks the beginning and the end of the seat reservations influence. After processing all bookings, taking the prefix sum of this difference array yields the total seats reserved for each flight.

Code Solutions

# Python solution using a difference array
def corpFlightBookings(bookings, n):
    # Initialize difference array with zeros
    diff = [0] * (n + 1)  # n+1 size to handle end boundary
    
    # Process each booking and update the diff array
    for start, end, seats in bookings:
        diff[start - 1] += seats  # add seats at the start index (0-based)
        if end < n:
            diff[end] -= seats  # subtract seats just after the end index
    
    # Accumulate the difference array to form the answer array
    answer = [0] * n
    current = 0
    for i in range(n):
        current += diff[i]
        answer[i] = current
        
    return answer

# Example usage:
# bookings = [[1,2,10],[2,3,20],[2,5,25]]
# n = 5
# print(corpFlightBookings(bookings, n))
← Back to All Questions