Patrol Coverage

Medium · rating 1500 · Intervals, Sorting

Guards patrol segments of a corridor. The first line has n. Each of the next n lines has l r, a patrolled segment [l, r]. Print the total length of corridor covered by at least one guard (the length of the union; each segment's length is r - l).

Constraints: 1 ≤ n ≤ 105

Editorial

Approach

Sort the segments by start and sweep, keeping one running merged segment. Extend it while the next segment overlaps; when a gap appears, bank the finished segment's length and start a new one. The banked lengths sum to the union.

for l, r in sorted(segments):
    if r_cur is None: l_cur, r_cur = l, r
    elif l <= r_cur: r_cur = max(r_cur, r)
    else: total += r_cur - l_cur; l_cur, r_cur = l, r
total += r_cur - l_cur

Complexity

Time: O(n log n). Space: O(n).

Related problems

Open Patrol Coverage in Code Arena →