1446. The Free Stretches Inside the Working Day

The working day is the HALF-OPEN stretch [0, T). n bookings are given, each a half-open interval [a, b) with a < b. Bookings arrive in no particular order, may overlap each other, and may stick out past either end of the day or lie entirely outside it.

Print every maximal stretch of the day during which nothing is booked. A stretch counts only if it has POSITIVE length.

T = 20, bookings [2,5) [9,12) [15,16) -> [0,2) [5,9) [12,15) [16,20) T = 10, bookings [0,4) [4,10) -> nothing free T = 10, bookings [3,4) -> [0,3) [4,10)

The middle line is the endpoint rule. [0,4) stops just short of 4 and [4,10) starts at 4, so between them there is no point at all, and in particular no free stretch of positive length. A solution that reports [4,4) there has produced an empty answer and called it a gap.

## What most people try first

Walking the day one unit at a time and marking booked units. That is correct and costs O(T) per query with T reaching 10^9, so it never finishes.

The second reflex is to sort the bookings and read off the gap between each consecutive pair. That is right when the bookings are tidy and wrong when they overlap: with [0,10) and [2,3) the consecutive pair reports a gap from 10 back to 2, a negative length, and a program that prints it emits a stretch running backwards.

## Clip, sort, sweep

clip each booking to the day: a = max(a, 0), b = min(b, T) throw it away if a >= b it was entirely outside the day sort what is left by START cur = 0 for each [a, b): if a > cur: emit [cur, a) a genuine free stretch cur = max(cur, b) never let cur go backwards if cur < T: emit [cur, T)

Sorting is O(n log n) and the sweep is one pass. The clipping is what makes bookings outside the day harmless without a special case in the loop.

## Why cur must be a running maximum

cur means everything before it is accounted for. A booking that lies wholly inside an earlier one has a smaller end, and writing cur = b would move the frontier backwards and invent a free stretch that is really booked. Taking the maximum makes cur non-decreasing, which is the invariant the whole sweep rests on: a stretch is emitted only when the next booking starts strictly after the frontier, and the frontier only ever moves forward.

## The boundary that breaks a careless implementation

Emit only when a > cur, strictly. Two bookings that touch give a == cur and there is nothing between them. The same applies at the far end: emit the tail only when cur < T, or a day whose last booking ends exactly at T produces a final empty stretch.

The head is worth its own thought. The sweep starts at cur = 0 rather than at the first booking, so a day with no booking before time 5 correctly reports [0,5) as free. Starting cur at the first booking's start loses it.

## Overflow

T and the coordinates reach 10^9, so every number printed fits in a signed 32 bit integer, whose limit is 2147483647. No sums are taken, so nothing accumulates. The output can hold up to n + 1 stretches, so build it in one string rather than printing inside the loop.

## Related

Problem 931 finds free stretches across k lists that are each already sorted, and reports them between the earliest start and the latest end of everything given, with no explicit window. This one is handed one messy list and a fixed window, so clipping and the two open ends of the day are the work. Problem 1444 removes a second list instead of complementing within a window.

Constraints - `1 ≤ T ≤ 10^9` - `0 ≤ n ≤ 200000` - `-10^9 ≤ a < b ≤ 10^9` for every booking - the day and every booking are half-open, `[a, b)` - bookings arrive in no particular order, may overlap, and may lie partly or wholly outside the day