562. Tightest Range Over Lists
A city has several bus routes, and the array lists holds, for each route, the minutes after midnight at which its buses depart, in any order. A traveller wants one departure from every route that all happen inside one time window [a, b], and wants that window as short as possible.
Find the window [a, b] with the smallest length b - a such that every list has at least one value v with a <= v <= b. If several windows have the same length, return the one with the smaller a. Return it as the array [a, b].
With N values in total and k lists, the intended solution takes O(N log N) time (sorting each list, then merging with a heap) and O(N) extra space.
Example 1
- Input:
- lists = [[2,8,14],[3,9,20],[10,11,25]]
- Output:
- [8,10]
- Explanation:
The window [8, 10] contains 8, 9 and 10, one value from each list, and no window of length 1 or 0 does.
Example 2
- Input:
- lists = [[1,3,5],[2,4,6]]
- Output:
- [1,2]
- Explanation:
Several windows have length 1; the smallest start wins, so [1, 2] is returned.
Example 3
- Input:
- lists = [[7],[7],[7]]
- Output:
- [7,7]
- Explanation:
All lists contain only 7, so the window is [7, 7] of length 0.
Constraints
- 1 ≤
lists.length= k ≤ 104 - Every list is non-empty (not necessarily sorted); the total number of values N is at most 2 * 105
- -108 ≤ value ≤ 108
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 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(N log N)
- Space
- O(N)