The Basilisk Watches of Carrowgate Quarry

Commission of the Carrowgate Stonecutters' Guild, posted at Bitwick

A basilisk has made its den in the deep pit of Carrowgate Quarry. Each night it lifts its head and sweeps its gaze across the quarry floor, sometimes once and sometimes many times, and the sweeps may overlap. The Guild's watchers have recorded every sweep for tonight. They need a reckoning of the stretches when no gaze falls on the floor at all, so that cutters can be sent down to haul out the abandoned marble. A stretch is only worth the risk if it is long enough to do the work.

Write safeWindows(gazes, dusk, k).

Arguments - gazes: a list of pairs [start, end] of integers, in no particular order, with 0 <= start < end <= dusk. Each pair means the floor is under the gaze from minute start up to but not including minute end (a half-open span). Pairs may overlap, nest inside one another, touch end-to-start, or repeat. The list may be empty. - dusk: an integer >= 0. The night is the half-open span from minute 0 up to but not including minute dusk. - k: an integer >= 1, the shortest stretch the cutters will accept.

Return a list of pairs [a, b] of integers: every maximal span [a, b) inside [0, dusk) during which no gaze is active, keeping only those with b - a >= k. A maximal span cannot be extended in either direction without touching a gaze or leaving the night. Order the pairs by a, ascending. If no span qualifies, return an empty list.

Two gazes where one ends at the minute the other starts leave no gap between them.