Problem Description
Given an array of flight bookings where each booking specifies a range of flights and the number of seats reserved for each flight in that range, return an array representing the total number of seats reserved for each flight.
Key Insights
- Flight bookings can affect multiple flights in a continuous range.
- Using a prefix sum technique allows for efficient updates and calculations over ranges.
- We can utilize a difference array to handle the seat reservations efficiently.
Space and Time Complexity
Time Complexity: O(k + n), where k is the number of bookings and n is the number of flights.
Space Complexity: O(n), for the result array and the auxiliary storage.
Solution
To solve this problem, we can use a difference array approach. We initialize an array of zeros with a length of n + 1 to account for the range updates. For each booking, we increment the starting index of the flight by the number of seats and decrement the index right after the last flight by the same number. This allows us to mark the beginning and end of the seat reservations.
After processing all bookings, we iterate through the difference array to calculate the prefix sum, which gives us the total seats reserved for each flight.