Days Off the Calendar
EasyIntervalsFree
Problem
An employee is available on days 1 to days inclusive. The list meetings holds blocks of days she is booked: meetings[i] = [start, end] books every day from start to end, both inclusive. Blocks may overlap.
Return how many days in 1..days have no meeting at all.
Example 1
- Input:
- days = 10, meetings = [[5, 7], [1, 3], [9, 10]]
- Output:
- 2
Days 1–3, 5–7 and 9–10 are booked (8 days). Days 4 and 8 are free.
Example 2
- Input:
- days = 5, meetings = [[2, 4], [1, 3]]
- Output:
- 1
Together the blocks cover days 1–4; only day 5 is free.
Constraints
- 1 ≤ days ≤ 10^9
- 0 ≤ meetings.length ≤ 10^5
- 1 ≤ start ≤ end ≤ days
Hint
Show the first hint
days can be a billion, so you cannot mark days one by one. What can you count instead?
Walkthrough
How to approach it
01Clarify before coding
- Are both endpoints booked? Yes: [5, 7] books days 5, 6 and 7.
- Can blocks overlap or repeat? Yes, so the same day may appear in several blocks.
- How large can
daysbe? Up to 10^9, which rules out a per-day array.
02Brute force
Keep a boolean per day, mark every day of every block, then count the unmarked days.
Cost: O(days + total block length) time and O(days) memory: a billion booleans is not an option.
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.