A venue's bookings are given as n half-open intervals [start, end). After merging overlapping or touching bookings into solid blocks, report the length of the longest free gap that lies strictly between two consecutive blocks. If there is at most one block (hence no in-between gap), report 0. Free time before the first block or after the last block does not count.
Line 1: an integer n.
Next n lines: two integers start end (with start < end).
A single integer: the length of the longest gap between consecutive blocks (0 if none).
Example 1
Input
3 0 2 5 6 20 25
Expected
14
Explanation
Blocks [0,2), [5,6), [20,25) leave gaps [2,5) of length 3 and [6,20) of length 14; the longest is 14.
Example 2
Input
2 0 5 2 8
Expected
0
Explanation
The bookings merge into one block [0,8), so there is no in-between gap: 0.
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 →