There are k sensors, and each sensor reports a non-empty list of integer readings sorted in non-decreasing order. Find the smallest inclusive band [lo, hi] (with lo <= hi) such that every sensor has at least one reading r with lo <= r <= hi.
Minimize the band width hi - lo. If several bands achieve the minimum width, choose the one with the smallest lo. It is guaranteed that lo and hi can be chosen as actual readings.
Line 1: an integer k, the number of sensors.
Next k lines: each line starts with an integer L >= 1 (the number of readings for that sensor) followed by L non-decreasing integers.
Two integers lo and hi on one line, separated by a space: the endpoints of the smallest covering band.
Example 1
Input
3 3 1 5 9 3 4 7 10 2 3 6
Expected
3 5
Explanation
The band [3,5] contains 5 (sensor 1), 4 (sensor 2), and 3 (sensor 3). Its width 2 is minimal, and among width-2 bands it has the smallest lo, so the answer is 3 5.
Example 2
Input
2 1 10 3 2 6 10
Expected
10 10
Explanation
Sensor 1 only reads 10, so the band must include 10. Since sensor 2 also reads 10, the band [10,10] of width 0 covers both.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →