1486. Which Booking Clashes With the Most Others

n bookings are given, numbered from 1 in the order they appear. Booking i occupies the CLOSED stretch [a, b] with a <= b, so a booking ending at t and one starting at t DO clash: they share the moment t.

Print two integers on one line: the largest number of OTHER bookings any single booking clashes with, and the smallest number of a booking achieving it.

[1,5] [2,6] [8,9] [3,4] -> 2 1 [1,3] [3,5] [5,7] -> 2 2 [1,2] [5,6] [9,10] -> 0 1

The middle line is the convention. Booking 2 runs from 3 to 5 and shares the moment 3 with booking 1 and the moment 5 with booking 3, so it clashes with two. Bookings 1 and 3 clash with one each. Under a HALF-OPEN reading none of them would clash with anything and the answer would be 0 1. Bookings that merely TOUCH still clash here, and that is what the whole answer turns on.

The third line shows that the answer can be 0, and that the tie among all the zeroes is broken by the smallest booking number.

## What most people try first

Two nested loops testing every pair. It is exactly right and it is O(n^2): at n = 200000 that is 4 * 10^10 pair tests, and the answer can genuinely be n - 1, so no pruning saves it either.

## Count what does NOT clash

Booking j fails to clash with booking i exactly when it lies entirely to one side: a_j > b_i or b_j < a_i. Those two cases cannot both hold, since that would give a_j > b_i >= a_i > b_j >= a_j. And neither holds for j = i, since a_i <= b_i. So for booking i

clashes[i] = (n - 1) - #{ j : a_j > b_i } - #{ j : b_j < a_i }

Both counts are answered by a binary search once the starts and the ends are each in their own sorted array:

S = every a, sorted; E = every b, sorted for each booking i: right = how many entries of S are strictly greater than b_i left = how many entries of E are strictly less than a_i clashes = n - 1 - right - left

O(n log n).

## Why the two counts never overlap and never include the booking itself

If a_j > b_i and b_j < a_i both held, then a_j > b_i >= a_i > b_j, and a_j > b_j contradicts a_j <= b_j. So each non-clashing partner is counted once, on exactly one side.

Booking i is in neither count: a_i > b_i is false and b_i < a_i is false. So n - 1 - right - left really is the number of OTHER bookings that clash, with no correction needed.

## The boundary that breaks a careless implementation

Both comparisons are STRICT. A booking starting exactly at b_i clashes under the closed reading and must not be counted among the non-clashers, and likewise for one ending exactly at a_i. Making either non-strict turns the middle sample into 0 1.

Ties on the count are broken by the smallest booking NUMBER, so record a new best only on a strict improvement while walking the bookings in input order.

## Overflow

The count is at most n - 1 = 199999 and the coordinates reach 10^9, both inside the 2147483647 a signed 32 bit integer holds. Nothing is summed, which is worth noticing next to problem 1456, where the same shape of question about PAIRS reaches 2 * 10^10 and needs 64 bits.

## Related

Problem 1456 counts the clashing pairs in total rather than per booking, and its answer needs 64 bits where this one does not. Problem 1487 asks which booking CONTAINS the most others, which is a two-sided dominance count and needs a structure rather than two binary searches. Problem 1448 asks how many clash at one moment, which is a different quantity again.

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a ≤ b ≤ 10^9` - each booking occupies the closed stretch `[a, b]`, so sharing an endpoint counts as clashing - `a == b` is allowed and means a booking occupying a single moment