A corner shop is open whenever at least one employee is on shift. Each shift is a pair (start, end) in minutes with start < end, covering the time from start up to but not including end. Shifts can overlap, and a shift that starts exactly when another ends is a handover: the shop stays open without a break.
Write longest_open(shifts: list[tuple[int, int]]) -> int that returns the length, in minutes, of the longest unbroken stretch during which the shop is open, or 0 if there are no shifts. The shifts are in no particular order.
longest_open([(540, 600), (720, 780), (590, 660)]) # 120 540..660, the 720..780 stretch is only 60
longest_open([(0, 10), (10, 20), (25, 30)]) # 20 handover at 10 keeps it open 0..20
longest_open([(5, 50), (10, 20)]) # 45 a shift inside another adds nothing
Constraints: up to 10^5 shifts, times between -10^9 and 10^9. Your answer should be O(n log n).
Show hint
sort by start and sweep, keeping the current stretch's start and end: a shift with start <= end extends the stretch to max(end, shift_end); otherwise the stretch is over, so record its length and begin a new one.