Find Available Booking Windows
As an Airbnb host, managing your listing's availability is crucial. Guests often search for specific durations, and hosts need to quickly identify if and when their listing can accommodate a new booking. This problem simulates a core part of that availability check, focusing on finding all valid windows for a new booking given existing reservations.
Given a list of existing, confirmed bookings (unavailable time intervals) for an Airbnb listing, a desiredDuration for a new booking, and an overall searchRange, your task is to identify and return all contiguous time intervals where a new booking of desiredDuration can start. The returned intervals should represent the earliest possible start time up to the latest possible start time for such a booking within a continuous available slot.
Function Signature:
function findAvailableBookingWindows(existingBookings: number[][], desiredDuration: number, searchRange: number[]): number[][]
Input:
existingBookings: An array of [start, end] integer arrays, representing time intervals when the listing is already booked and thus unavailable. These intervals are [start, end) (inclusive start, exclusive end). They may be unsorted and can overlap.desiredDuration: A positive integer representing the length (in the same time units as start/end) of the new booking a guest wishes to make.searchRange: A [rangeStart, rangeEnd] integer array, defining the overall time horizon [rangeStart, rangeEnd) within which to find available windows. All returned windows must fall within this range.Output:
[start, end] integer arrays. Each [start, end] in the output represents a continuous block of time where a booking of desiredDuration could start. Specifically, if an available gap is [gapStart, gapEnd), and gapEnd - gapStart >= desiredDuration, then a new booking of desiredDuration can start at any time t such that gapStart <= t <= gapEnd - desiredDuration. The output interval should be [gapStart, gapEnd - desiredDuration]. The output intervals should be sorted by their start times.[start, end): inclusive of start, exclusive of end. For example, [10, 20) means from time 10 up to (but not including) time 20.existingBookings is empty, the entire searchRange is considered available.desiredDuration will always be a positive integer.searchRange will always be [start, end] where start < end.[].Examples
Example 1
Input:
existingBookings = [[10, 20], [30, 40]], desiredDuration = 5, searchRange = [0, 50]
Output:
[[0, 5], [20, 25], [40, 45]]
Note:
The available gaps are [0, 10), [20, 30), and [40, 50). Each has a length of 10. For a desiredDuration of 5, each gap [G_start, G_end) allows bookings to start from G_start up to G_end - 5. Thus, [0, 5], [20, 25], and [40, 45] are the valid start windows.
Example 2
Input:
existingBookings = [[1, 5], [3, 7], [10, 12]], desiredDuration = 3, searchRange = [0, 15]
Output:
[[7, 7], [12, 12]]
Note:
First, merge existing bookings: [[1, 7], [10, 12]]. Available gaps within [0, 15): [0, 1) (length 1), [7, 10) (length 3), [12, 15) (length 3). For desiredDuration = 3:
Example 3
Input:
existingBookings = [[0, 100]], desiredDuration = 10, searchRange = [0, 100]
Output:
[]
Note:
The entire searchRange [0, 100) is covered by an existing booking. There are no available gaps to accommodate a new booking.
Constraints
0 <= existingBookings.length <= 10^40 <= existingBookings[i][0] < existingBookings[i][1] <= 10^91 <= desiredDuration <= 10^90 <= searchRange[0] < searchRange[1] <= 10^9O(N log N) where N is the number of existing bookings.searchRange and the merged unavailable intervals.desiredDuration to filter gaps and transform them into valid booking start windows.desiredDuration, and handling of searchRange boundaries.Loading editor...