LeetCode: Corporate Flight Bookings

Posted on August 5, 2019July 26, 2020 by braindenny

Corporate Flight Bookings

Similar Problems:

There are n flights, and they are labeled from 1 to n.

We have a list of flight bookings. The i-th booking bookings[i] = [i, j, k] means that we booked k seats from flights labeled i to j inclusive.

Return an array answer of length n, representing the number of seats booked on each flight in order of their label.

Example 1:

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]

Constraints:

1 <= bookings.length <= 20000
1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000
1 <= bookings[i][2] <= 10000

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution: Without addtional space

// https://code.dennyzhang.com/corporate-flight-bookings
// Basic Ideas: combined caculation
//
// Complexity: Time O(n), Space O(1)
func corpFlightBookings(bookings [][]int, n int) []int {
    res := make([]int, n)
    for _, b := range bookings {
        res[b[0]-1] += b[2]
        if b[1] < n {
            res[b[1]] -= b[2]
        }
    }
    for i:=1; i<n; i++ {
        res[i] += res[i-1]
    }
    return res
}

Solution: With addtional space

// https://code.dennyzhang.com/corporate-flight-bookings
// Basic Ideas: combined caculation
//
// Complexity: Time O(n), Space O(n)
func corpFlightBookings(bookings [][]int, n int) []int {
    l := make([]int, n+2)
    for _, b := range bookings {
        l[b[0]] += b[2]
        l[b[1]+1] -= b[2]
    }
    res := make([]int, n)
    count:=0
    for i:=1; i<=n; i++ {
        count+=l[i]
        res[i-1] = count
    }
    return res
}

Post Views: 0