Frontend School

Find Available Booking Windows

DSA
medium

Find Available Booking Windows

Medium
Intervals
Sorting
Greedy

Overview

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.

What you need to do / Task

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.

Input & output

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:

  • An array of [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.

Clarifications

  • All time units (start, end, duration) are positive integers.
  • Intervals are [start, end): inclusive of start, exclusive of end. For example, [10, 20) means from time 10 up to (but not including) time 20.
  • If 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.
  • If no suitable windows are found, return an empty array [].

Examples

1

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.

2

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:

  • [0, 1) is too short.
  • [7, 10) has length 3. Valid start window: [7, 10 - 3] = [7, 7].
  • [12, 15) has length 3. Valid start window: [12, 15 - 3] = [12, 12].
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

Constraints & assumptions

  • 0 <= existingBookings.length <= 10^4
  • 0 <= existingBookings[i][0] < existingBookings[i][1] <= 10^9
  • 1 <= desiredDuration <= 10^9
  • 0 <= searchRange[0] < searchRange[1] <= 10^9
  • All time values are integers.
  • The problem asks for an efficient solution, typically O(N log N) where N is the number of existing bookings.

What interviewers evaluate

  • Correctness of Interval Merging: Ability to consolidate overlapping and unsorted existing bookings into a clean, non-overlapping list of unavailable time.
  • Gap Identification: Accurately determine all available time gaps by comparing searchRange and the merged unavailable intervals.
  • Duration Filtering: Correctly apply desiredDuration to filter gaps and transform them into valid booking start windows.
  • Edge Case Handling: Robustness against empty booking lists, gaps smaller than desiredDuration, and handling of searchRange boundaries.
  • Optimal Complexity: Implementation that achieves the optimal time and space complexity for this type of interval problem.

Loading editor...