Corporate Flight Bookings

August 16, 2019

Introduction

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

Solution

Simple strait-forward solution would be a bruteforce one. Let’s implement it first.

func corpFlightBookings(bookings [][]int, n int) []int {
    
    out := make([]int, n)
    
    for _, b := range bookings {
        x, y, k := b[0], b[1], b[2]
        for i := x; i <= y; i++ {
            out[i-1] += k
        }
    }
    
    return out
    
}

Another way to solve this problem is to keep track of visited intervals in cache.

type interval struct {
    last int
    cnt  int
}

func put(cache map[int]*interval, first, last, k int) {
    
    if inter, ok := cache[first]; ok {

        if inter.last == last {
            inter.cnt += k
        } else if inter.last < last {
            inter.cnt += k
            put(cache, inter.last + 1, last, k)
        } else {
            put(cache, last+1, inter.last, inter.cnt)
            inter.cnt += k
            inter.last = last
        }
        
    } else {
        cache[first] = &interval{ last, k }
    }
}

func corpFlightBookings(bookings [][]int, n int) []int {
    
    cache := make(map[int]*interval)
    
    for _, b := range bookings {
        first, last, k := b[0], b[1], b[2]
        put(cache, first, last, k)
    }
    
    out := make([]int, n)
    for k, v := range cache {
        for i := k; i <= v.last; i++ {
            out[i-1] += v.cnt
        }
    }
    
    return out
    
}

Fastest way to solve this problem is to calculate sum of all visits:

func corpFlightBookings(bookings [][]int, n int) []int {
	
 out := make([]int, n+1)
    
	for _, b := range bookings {
		 first, last, k := b[0], b[1], b[2]
		 out[first-1] += k
		 out[last] -= k
	}

	for i := 1; i < n; i++ {
		 out[i] += out[i-1]
	}

	return out[:n]
}