Smallest Range Covering Every List

A group of friends wants to meet in an online game, and each friend has sent a list of the minutes (after noon) at which they can log in, sorted from earliest to latest. lists holds one such list per friend. You are looking for the narrowest window of time (low, high) that holds at least one login minute of every friend: every list has a number x with low <= x <= high.

Write smallest_range(lists) that returns that window as a tuple (low, high). The width of a window is high - low. If several windows are equally narrow, return the one with the smallest low.

Examples

smallest_range([[1, 7, 12], [3, 9, 20], [8, 15]])   # returns (7, 9)
smallest_range([[5], [5], [5]])                      # returns (5, 5)
smallest_range([[1, 2, 3], [10, 11], [4, 20]])       # returns (3, 10)
smallest_range([[1, 6], [3, 8]])                     # returns (1, 3)

In the first example the window from 7 to 9 holds 7 from the first list, 9 from the second and 8 from the third. In the last example (1, 3) and (6, 8) are equally narrow, and (1, 3) starts earlier.

Constraints

• 1 <= len(lists) <= 1,000
• Every list holds at least one number, and all the lists together hold at most 100,000
• -10^9 <= lists[i][j] <= 10^9, and each list is sorted from smallest to largest (numbers can repeat)

Note

Trying every possible start of the window against every list is far too slow for a thousand lists.