A logging service records busy periods as half-open segments [start, end) on an integer timeline. Because periods can overlap, you want the total amount of time that is busy at all: the length of the union of the segments. A point is counted once no matter how many segments cover it.
Formally, output the measure of the set of real numbers x such that start <= x < end for at least one segment.
Line 1: an integer n — the number of segments.
Next n lines: two integers start end describing one segment [start, end).
A single integer: the total length of the union of all segments.
Overlap then a gap
Input
3 1 4 2 5 7 9
Expected
6
Explanation
[1,4) and [2,5) merge into [1,5) with length 4. [7,9) is separate with length 2. Total union length is 4 + 2 = 6.
Touching segments
Input
2 0 3 3 6
Expected
6
Explanation
[0,3) and [3,6) share only the point 3 (which is excluded from [0,3)), so together they cover [0,6) with length 6, no double counting.
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 →