Shared Exposure Windows

Count the start times at which an observatory array can begin a long exposure that keeps enough telescopes free throughout.

A night lasts length minutes, numbered 0 to length - 1. A long exposure takes window consecutive minutes: started at minute t, it occupies minutes t to t + window - 1, and must finish within the night, so 0 <= t <= length - window. It needs k different telescopes, and each of them has to be free for the whole exposure (a telescope that is free for the first half and a different one for the second half do not count together).

Each telescope has a list of maintenance bookings [start, end): it is busy during minutes start to end - 1, so a booking that ends at end leaves minute end free, and a booking with start = end is empty. Bookings of one telescope may overlap, nest, touch each other, and come in any order.

An exposure starting at t is possible if at least k telescopes have no busy minute among t .. t + window - 1.

Input: length, the minutes in the night; window, the exposure length; k, the number of telescopes needed; bookings, one list of [start, end] pairs per telescope (0 <= start <= end <= length).

Output: the number of start times t at which an exposure is possible. If window > length or fewer than k telescopes exist, the answer is 0.