Practice/Google/Leetcode 1109. Corporate Flight Bookings

Leetcode 1109. Corporate Flight Bookings

CodingMust

Problem

You are managing seat reservations for an airline with n flights numbered from 1 to n. You receive a list of booking requests where each booking is represented as [first, last, seats], indicating that seats number of seats should be reserved on every flight from first to last (inclusive).

Your task is to return an array of length n where the value at index i represents the total number of seats reserved for flight i+1.

Requirements

1. Process all booking requests and calculate the cumulative seat reservations for each flight
2. Each booking applies to a continuous range of flights
3. Return an array where element at index i contains total reserved seats for flight i+1
4. Handle overlapping booking ranges efficiently

Constraints

• 1 ≤ n ≤ 20,000
• 1 ≤ bookings.length ≤ 20,000
• bookings[i].length == 3
• 1 ≤ first_i ≤ last_i ≤ n
• 1 ≤ seats_i ≤ 10,000
• Your solution should handle the maximum input size efficiently

Examples

Example 1:

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 Output: [10,55,45,25,25] Explanation: Flight 1: booking 1 adds 10 seats → total = 10 Flight 2: bookings 1,2,3 add 10+20+25 seats → total = 55 Flight 3: bookings 2,3 add 20+25 seats → total = 45 Flight 4: booking 3 adds 25 seats → total = 25 Flight 5: booking 3 adds 25 seats → total = 25

Example 2:

Input: bookings = [[1,2,10],[2,2,15]], n = 2 Output: [10,25] Explanation: Flight 1: only booking 1 applies → 10 seats Flight 2: both bookings apply → 10+15 = 25 seats

Example 3:

Input: bookings = [[1,3,50]], n = 3 Output: [50,50,50] Explanation: Single booking reserves 50 seats on all three flights