Carve Out a Window
MediumIntervals
Problem
A shared calendar stores free time as intervals: half-open ranges [start, end), sorted by start and pairwise disjoint. Someone books the half-open window = [from, to).
Return the free time that remains: the parts of intervals outside the window, still sorted and disjoint. Drop any piece that becomes empty.
Example 1
- Input:
- intervals = [[0, 2], [3, 4], [5, 7]], window = [1, 6]
- Output:
- [[0, 1], [6, 7]]
The booking eats [1, 2), all of [3, 4) and [5, 6).
Example 2
- Input:
- intervals = [[0, 5]], window = [2, 3]
- Output:
- [[0, 2], [3, 5]]
A booking in the middle splits one free range into two.
Constraints
- 0 ≤ intervals.length ≤ 10^5
- -10^9 ≤ start < end ≤ 10^9
- -10^9 ≤ from < to ≤ 10^9
Hint
Show the first hint
Treat each free interval on its own. What can the window do to a single interval?
Walkthrough
How to approach it
01Clarify before coding
- Are the ranges half-open? Yes: removing [3, 5) from [1, 3) leaves [1, 3) untouched.
- Should empty pieces be returned? No, drop them.
- Is the input sorted? Yes, and the output must stay sorted.
02Brute force
Expand every interval into its individual time units, delete those inside the window and rebuild ranges.
Cost: Proportional to the total length, up to 2·10^9 units: impossible.
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.