1456. How Many Pairs Clash
n reservations are given. Reservation i occupies the CLOSED stretch
[a, b] with a <= b, so a reservation ending at t and one starting at t
DO clash: they share the moment t.
Print how many unordered pairs of reservations clash.
[1,5] [2,6] [8,9] [3,4] -> 3
[1,3] [3,5] [5,7] -> 2 the two touching pairs
[1,2] [3,4] [5,6] -> 0
The middle line is the convention. Under a HALF-OPEN reading those three would clash in no pairs at all. Closed means the shared endpoint counts, and that is what turns the answer from 0 into 2.
## What most people try first
Two nested loops testing max(a1, a2) <= min(b1, b2). It is exactly right and
it is O(n^2): at n = 200000 that is about 2 * 10^10 pair tests.
The count itself rules out any clever pruning. If every reservation covers the
whole day, all n (n - 1) / 2 pairs clash, which is about 2 * 10^10 pairs,
so no method that touches each clashing pair individually can ever be fast
enough. The pairs have to be COUNTED rather than visited.
## Count the pairs that do NOT clash
Two closed intervals fail to clash exactly when one lies entirely to the right
of the other, that is when a2 > b1 or a1 > b2. For an unordered pair
exactly one of those can hold, since a1 <= b1 and a2 <= b2, so each
non-clashing pair is counted once by
sort all the START coordinates into one array S
apart = 0
for each reservation [a, b]:
apart += (how many entries of S are strictly greater than b)
answer = n (n - 1) / 2 - apart
Each count is a binary search on S, so the whole thing is O(n log n), about
3.5 * 10^6 steps at the limits.
## Why each non-clashing pair is counted exactly once
Take a pair that does not clash. One of them ends before the other begins, say
b1 < a2. Then a2 is strictly greater than b1 and the pair is counted when
the loop reaches reservation 1. Could it also be counted at reservation 2, that
is, could a1 > b2? That would give a1 > b2 >= a2 > b1 >= a1, which says
a1 > a1. So no: exactly one of the two directions holds, and the count is a
count of pairs rather than of ordered pairs.
A reservation is never counted against itself either, since a <= b means its
own start is not strictly greater than its own end.
## The boundary that breaks a careless implementation
Strictly greater, not at least. A reservation starting exactly at another's end
CLASHES under the closed reading, so it must not be counted among the apart
pairs. Using >= b there answers 0 on the middle sample instead of 2.
a == b is legal and means a reservation occupying a single moment. Five of
them at the same moment clash in all ten pairs.
## Overflow
n (n - 1) / 2 at n = 200000 is 19999900000, about 2 * 10^10. A signed
32 bit integer holds 2147483647, so the answer is past it by roughly a factor
of nine and the counter must be 64 bit. Note the product n * (n - 1) must
itself be computed in 64 bit: doing it in 32 and then widening loses the answer
before the division ever runs.
## Related
Problem 1458 counts only the pairs whose shared part is a single point, which is a subset of these and needs no sorting at all. Problem 1486 asks which single reservation clashes with the most others. Problem 1448 asks for the largest number of reservations clashing at one moment, which is a different quantity: pairwise clashes do not add up to a common moment.
Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a ≤ b ≤ 10^9` - each reservation is the closed stretch `[a, b]`, so touching at an endpoint counts as clashing - `a == b` is allowed and means a reservation occupying a single moment
Input
The first line contains the integer n.
Each of the next n lines contains two integers a and b, one reservation, in no particular order.
Output
Print one integer alone on its own line: the number of unordered pairs of reservations that share at least one moment, counting a shared endpoint as sharing. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.