Free for Everyone
MediumIntervals
Problem
A team of people members, numbered 0 to people - 1, shares its availability as slots. Each slot is [person, start, end]: that person is available during the half-open range [start, end). One person's slots never overlap each other, though they may touch.
Return every maximal time range during which all members are available, as half-open [start, end] pairs sorted by start. Ranges must have positive length, and touching ranges must be reported as one.
Example 1
- Input:
- people = 2, slots = [[0, 1, 5], [0, 7, 10], [1, 3, 8]]
- Output:
- [[3, 5], [7, 8]]
Person 0 is free in [1, 5) and [7, 10), person 1 in [3, 8). Both are free in [3, 5) and [7, 8).
Example 2
- Input:
- people = 2, slots = [[0, 1, 3], [0, 3, 5], [1, 0, 6]]
- Output:
- [[1, 5]]
Person 0's two slots touch at 3, so everyone is free throughout [1, 5).
Constraints
- 1 ≤ people ≤ 10^4
- 0 ≤ slots.length ≤ 10^5
- 0 ≤ person < people
- 0 ≤ start < end ≤ 10^9
- A person's slots are pairwise non-overlapping.
Hint
Show the first hint
Since no person double-books themselves, how many people are available at time t is just how many slots contain t.
Walkthrough
How to approach it
01Clarify before coding
- Can a person have overlapping slots? No, which is what lets a simple count stand for 'number of people available'.
- What if some person has no slots? Then nobody-free-together: return [].
- Should touching output ranges be merged? Yes, report maximal ranges.
02Brute force
Merge each person's slots, then intersect the lists pairwise, person by person, with two pointers.
Cost: O(people · n) in the worst case, since the running intersection can be re-scanned for each person; correct but clumsy.
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.