Longest Free Gap
EasyIntervals
Problem
A shared lab instrument has a list of bookings, each a half-open range [start, end). Bookings may overlap.
Between the first booking's start and the last booking's end, find the longest stretch of time in which the instrument is not booked at all. Return its length, or 0 if there is no free time in between.
Example 1
- Input:
- bookings = [[1, 3], [6, 8], [2, 4]]
- Output:
- 2
Booked time is [1, 4) and [6, 8); the free gap [4, 6) is 2 long.
Example 2
- Input:
- bookings = [[1, 2], [10, 11], [4, 5]]
- Output:
- 5
Gaps are [2, 4) and [5, 10); the second is longer.
Example 3
- Input:
- bookings = [[1, 5], [5, 9]]
- Output:
- 0
Constraints
- 1 ≤ bookings.length ≤ 10^5
- -10^9 ≤ start < end ≤ 10^9
Hint
Show the first hint
A gap only exists between the end of one booked block and the start of the next one.
Walkthrough
How to approach it
01Clarify before coding
- Do gaps before the first booking or after the last count? No, only gaps between bookings.
- Can bookings overlap? Yes; overlapping bookings form one busy block.
- Touching bookings like [1, 5) and [5, 9)? No gap between them.
02Brute force
For each booking end, scan all bookings for the nearest start that is not inside another booking.
Cost: O(n²) time.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.