74. Smallest Range Covering K Sorted Lists
Find a range on the number line that contains at least one occurrence from each supplied list. Minimize the range's width rather than the number of enclosed occurrences.
When several ranges have equal width, the contract prefers the one with the smaller starting value. Every input list must be represented.
Example 1
Input
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output
[20,24]
Explanation: It covers 24 from source 0, 20 from source 1, and 22 from source 2; narrower candidates cannot cover all three.
Example 2
Input
[[1,4],[2,5]]
Output
[1,2]
Explanation: [4,5] has the same width one, so the smaller start wins.
Example 3
Input
[[MIN],[MAX]]
Output
[MIN,MAX]
Explanation: This valid range has width above int capacity and exhausts a source immediately.
Constraints
1 <= lists.length <= 1041 <= lists[i].lengthsum(lists[i].length) <= 105-231 <= lists[i][j] <= 231 - 1- Every list is sorted in nondecreasing order.
Hints
Hint 1
Keep one current witness from each sorted list.
Hint 2
The smallest witness limits the left endpoint; keep the largest in a scalar.
Hint 3
Evaluate [held minimum,current maximum], then advance only that minimum’s source or stop if it is exhausted.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Covered frontier follows the limiting source
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
[20,24]