A working window spans positions 0 to day (inclusive of 0, exclusive of day). Several busy intervals, each a half-open [start, end) lying inside [0, day], block off time. A meeting needs a free slot of length exactly need, i.e. an interval [t, t + need) that overlaps no busy interval and stays within [0, day]. Report the smallest such start time t, or -1 if no free slot of that length exists.
Line 1: two integers day and need.
Line 2: an integer m, the number of busy intervals.
Next m lines: two integers start end (with 0 <= start < end <= day).
A single integer: the earliest valid start time, or -1 if none exists.
Example 1
Input
20 3 2 0 5 8 12
Expected
5
Explanation
Busy blocks are [0,5) and [8,12). The gap [5,8) has length 3, exactly enough, so the earliest free slot starts at 5.
Example 2
Input
10 4 1 2 6
Expected
6
Explanation
Before the busy block only [0,2) is free (length 2, too short). After it, [6,10) has length 4, so the earliest fitting slot starts at 6.
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 →