191. Common Free Slot
Two friends want to meet. Lists a and b hold the free time slots of each friend, written [start, end]. Within one friend's list the slots are sorted by start and never overlap.
Find the earliest meeting that fits in a free slot of both friends and lasts exactly duration minutes. Return it as [t, t + duration], where t is the smallest possible start. A meeting from t to t + duration fits in a slot [s, e] when s <= t and t + duration <= e. If there is no such time, return an empty list.
Example 1
- Input:
- a = [[1,4],[9,14]]b = [[0,2],[3,8],[10,20]]duration = 3
- Output:
- [10,13]
- Explanation:
The shared free times are [1,2], [3,4] and [10,14]. Only [10,14] is at least 3 minutes long, so the earliest meeting is [10,13].
Example 2
- Input:
- a = [[0,5]], b = [[6,9]], duration = 1
- Output:
- []
- Explanation:
The two friends never have free time in common, so the answer is empty.
Example 3
- Input:
- a = [[2,10]], b = [[2,10]], duration = 8
- Output:
- [2,10]
- Explanation:
Their free times match exactly and 8 minutes fills the whole slot: [2,10].
Constraints
1 ≤ a.length, b.length ≤ 105
0 ≤ start < end ≤ 109 for every slot
1 ≤ duration ≤ 109
Slots in each list are sorted by start and do not overlap
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(1)