1454. Where to Put the Fixed-Width Window

n programmes are broadcast. Programme i runs over the HALF-OPEN stretch [a, b) with a < b. You may record for exactly w units of time, starting at any WHOLE moment x, so the recording covers [x, x + w).

A programme is CAUGHT when the recording and the programme share a stretch of POSITIVE length. Touching is not catching: a programme ending exactly when the recording starts is missed.

Print two integers on one line: the largest number of programmes one recording can catch, and the SMALLEST whole x that catches that many.

w=3, [1,5) [2,6) [8,9) [12,20) -> 2 0 w=1, [1,3) [3,5) [5,7) -> 1 1 w=2, [1,3) [3,5) [5,7) -> 2 2

Trace the first line. A recording starting at x = 0 covers [0, 3). It shares [1, 3) with [1,5) and [2, 3) with [2,6), so it catches two. Nothing catches three: the two long programmes run together only over [2, 5), and [8,9) begins two units after [2,6) ends, so no three-unit recording reaches both.

The second and third lines are the touching rule. With w = 1 a one-unit recording fits inside exactly one of the three programmes and can never straddle a shared endpoint, because touching is not catching. With w = 2 a recording at x = 2 covers [2, 4), catching [1,3) on [2,3) and [3,5) on [3,4).

## What most people try first

Trying every x. Whole moments run from about -2 * 10^9 to 10^9, so there are billions to try.

The second reflex is, for each programme, to test every other programme for whether some window catches both. That is O(n^2) and it answers the wrong question anyway, for the same reason as in problem 1448: pairwise agreement does not make a common window.

## Turn each programme into the set of window starts that catch it

Fix a programme [a, b). The recording [x, x + w) shares positive length with it exactly when

max(a, x) < min(b, x + w)

which splits into x < b and x + w > a, that is a - w < x < b. Over the whole numbers that is

a - w + 1 <= x <= b - 1

so every programme becomes a CLOSED range of good window starts, and the question becomes: which whole x lies in the most of those ranges? That is the maximum-load sweep of problem 1449, run on transformed input.

for each programme: event(a - w + 1, +1) and event(b - 1 + 1, -1) sort by coordinate walk the distinct coordinates, applying every event at each, and record the first coordinate that sets a new record

O(n log n).

## Why the transformed range is never empty

b - 1 >= a - w + 1 rearranges to b + w >= a + 2, and b >= a + 1 with w >= 1 gives b + w >= a + 2 immediately. So every programme is caught by at least one window, and the answer is at least 1. That is a useful sanity check: an implementation that can answer 0 has a sign error in the transform.

## Why the answer is always the left end of some transformed range

The load over the transformed ranges rises only at a left end, so the first whole x reaching the maximum is one of the a - w + 1 values. Recording a new best only on a strict improvement gives the smallest such x, exactly as in problem 1449.

## The boundary that breaks a careless implementation

Both +1 and -1 conversions are off by one from the obvious guess. The range is [a - w + 1, b - 1] and a closed range's closing event belongs at (b - 1) + 1 = b, so the pair is (a - w + 1, +1) and (b, -1). Writing (a - w, +1) treats a recording that merely touches the programme as catching it, and the middle sample then answers 2 rather than 1.

## Overflow

a - w + 1 reaches -10^9 - 10^9 + 1 = -1999999999. A signed 32 bit integer runs down to -2147483648, so that FITS, though with under 150 million to spare. Doing the subtraction in 64 bit costs nothing and removes the question. The count is at most n = 200000.

## Related

Problem 1449 is this sweep without the transform, on the intervals themselves. Problem 1093 lays down fixed-length strips to cover POINTS and asks for the fewest, a covering question rather than a counting one. Problem 715 slides a fixed window over an array; there the window's position is an index and here it is a coordinate that need not be an endpoint of anything.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ w ≤ 10^9` - `-10^9 ≤ a < b ≤ 10^9` - programmes and the recording are half-open, `[a, b)` and `[x, x + w)` - a programme is caught only when the shared stretch has positive length, so touching is not catching - `x` may be any whole number, including one outside the range of the programmes