The Mirage-Wards of the Saffron Waste

Commission of the Dune-Carters' Guild, posted at the Bitwick inn

The caravan track across the Saffron Waste runs straight from the Bitwick gate, at league 0, to the oasis of Qarsh Amun, at league length. Along it the Guild's hedge-mages have planted wardstones. Each wardstone throws its protection over one stretch of the track, from its start league to its end league. Some stretches overlap, some sit inside others, and some reach past either end of the track. Wherever the protection fails, the mirage-hounds hunt.

The Guild wants the open stretches of track charted before the next caravan sets out.

Write unwardedStretches(length, wards).

• length is a positive integer: the track covers every league from 0 to length.
• wards is a list of pairs [start, end] of integers with start < end. Each pair covers every point from start to end, endpoints included. The wards come in no particular order. A ward may start below 0 or end beyond length, and only its part on the track matters. The list may be empty.

Return a list of pairs [a, b], one for each maximal stretch of track with positive length that no ward covers. Each pair satisfies 0 <= a < b <= length. Here a is where the stretch begins: either 0 or the end of a ward. b is where it ends: either the start of a ward or length.

If one ward ends at the same league where another begins, nothing lies open between them. Return the pairs in ascending order of a. If the whole track is covered, return an empty list.