Smallest Range Touching Every Feed
Several sensors each produce a sorted list of timestamps; feeds[i] is the sorted list of sensor i. Find the smallest closed range [a, b] that contains at least one timestamp from every feed.
A range [a, b] is smaller than [c, d] if b - a < d - c, or if the widths are equal and a < c. Return the smallest range as [a, b].
Example 1
Input: feeds = [[1,5,8],[4,12],[7,8,10]] Output: [4,7] Explanation: 5 (feed 0), 4 (feed 1) and 7 (feed 2) fit in width 3, and nothing narrower works.
Example 2
Input: feeds = [[1,2,3],[1,2,3],[1,2,3]] Output: [1,1] Explanation: Every feed contains 1.
Constraints
- 1 <= feeds.length <= 50
- 1 <= feeds[i].length <= 500
- -10^5 <= feeds[i][j] <= 10^5
- Each feed is sorted in non-decreasing order.
Hint 1
Keep one pointer per feed and a min-heap of the values they point at, plus the current maximum.
Hint 2
The range [heap minimum, maximum] covers every feed; advance the feed that holds the minimum and repeat until a feed runs out.
Discussion 0
Join free to post in the discussion.
Good practice for: Data Engineer, Backend Developer, Data Scientist, Site Reliability Engineer, Machine Learning Engineer
Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.