Scale Engineer

Corporate Flight Bookings

Med
#1049Time: O(N * M), where N is the number of flights and M is the number of bookings. For each of the M bookings, we might iterate up to N flights in the worst case (e.g., a booking from flight 1 to N).Space: O(N), where N is the number of flights. We need an array of size N to store the seat counts.
Patterns
Prefix Sum
Data structures
Array

Prompt

There are n flights that are labeled from 1 to n.

You are given an array of flight bookings bookings, where bookings[i] = [firsti, lasti, seatsi] represents a booking for flights firsti through lasti (inclusive) with seatsi seats reserved for each flight in the range.

Return an array answer of length n, where answer[i] is the total number of seats reserved for flight i.

 

Example 1:

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]
Explanation:
Flight labels:        1   2   3   4   5
Booking 1 reserved:  10  10
Booking 2 reserved:      20  20
Booking 3 reserved:      25  25  25  25
Total seats:         10  55  45  25  25
Hence, answer = [10,55,45,25,25]

Example 2:

Input: bookings = [[1,2,10],[2,2,15]], n = 2
Output: [10,25]
Explanation:
Flight labels:        1   2
Booking 1 reserved:  10  10
Booking 2 reserved:      15
Total seats:         10  25
Hence, answer = [10,25]

 

Constraints:

  • 1 <= n <= 2 * 104
  • 1 <= bookings.length <= 2 * 104
  • bookings[i].length == 3
  • 1 <= firsti <= lasti <= n
  • 1 <= seatsi <= 104

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the booking process. We initialize an array to hold the seat counts for each flight. Then, for every booking, we iterate through the specified range of flights and add the number of seats to each flight in that range.

Algorithm

  • Create an integer array result of size n, initialized to all zeros.
  • Loop through each booking [first, last, seats] in the bookings array.
  • For each booking, run a nested loop from i = first to last.
  • Inside the nested loop, increment result[i-1] by seats. The subtraction of 1 is to convert the 1-based flight number to a 0-based array index.
  • After iterating through all bookings, the result array contains the final answer.

Walkthrough

The most straightforward way to solve the problem is to follow the description literally. We create an array representing the n flights and for each booking transaction, we iterate over the flights specified in the booking and add the corresponding number of seats. This process is repeated for all bookings.

class Solution {    public int[] corpFlightBookings(int[][] bookings, int n) {        int[] result = new int[n];        for (int[] booking : bookings) {            int first = booking[0];            int last = booking[1];            int seats = booking[2];            // Note: flights are 1-indexed, array is 0-indexed            for (int i = first - 1; i < last; i++) {                result[i] += seats;            }        }        return result;    }}

Complexity

Time

O(N * M), where N is the number of flights and M is the number of bookings. For each of the M bookings, we might iterate up to N flights in the worst case (e.g., a booking from flight 1 to N).

Space

O(N), where N is the number of flights. We need an array of size N to store the seat counts.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the problem statement.

Cons

  • Inefficient for large inputs, especially when booking ranges are wide.

  • Likely to cause a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits.

Solutions

class Solution {public  int[] corpFlightBookings(int[][] bookings, int n) {    int[] ans = new int[n];    for (var e : bookings) {      int first = e[0], last = e[1], seats = e[2];      ans[first - 1] += seats;      if (last < n) {        ans[last] -= seats;      }    }    for (int i = 1; i < n; ++i) {      ans[i] += ans[i - 1];    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem