Loading...
Loading...
Loading...
There are k sorted lists of integers. Find the smallest range [lo, hi] that contains at least one number from every list. A range is smaller than another if its length hi - lo is smaller, and if lengths are equal, the one with the smaller lo is smaller. Print lo and hi.
Example 1
Input
3 5 4 10 15 24 26 4 0 9 12 20 4 5 18 22 30
Output
20 24
The range 20 to 24 holds 20, 24 and 22.
Example 2
Input
1 3 2 5 9
Output
2 2
Try the problem first. Open one hint at a time.
Keep one current value per list in a min-heap, and track the largest of them.
The range is [heap top, current max]. Then replace the top by the next value of its list.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor