1487. Which Interval Swallows the Most Others

n intervals are given, numbered from 1 in the order they appear. Interval i is the CLOSED stretch [a, b] with a <= b. Interval i SWALLOWS interval j when

a_i <= a_j and b_j <= b_i

with both comparisons non-strict, so two intervals with exactly the same endpoints swallow each other.

Print two integers on one line: the largest number of OTHER intervals any single interval swallows, and the smallest number of an interval achieving it.

[1,4] [3,6] [2,8] -> 1 3 interval 3 swallows interval 2 [1,4] [2,3] [3,4] -> 2 1 interval 1 swallows both the others [1,2] [1,2] [1,2] -> 2 1 three copies, each swallowing the other two

The second line is worth tracing. [2,3] sits inside [1,4] because 1 <= 2 and 3 <= 4. [3,4] sits inside [1,4] because 1 <= 3 and 4 <= 4, and touching the right end still counts. So interval 1 swallows two.

The third line is the one that breaks most implementations. Identical intervals swallow each other, so each of the three swallows two. A solution that sorts and then counts only what comes AFTER in the sort order gives 2, 1, 0.

## What most people try first

Two nested loops. It is exactly right and it is O(n^2), which at n = 200000 is 4 * 10^10 pair tests. The answer can be n - 1, so the work is genuinely there.

The second attempt is to sort by start and keep a running maximum of the end, which decides whether an interval is swallowed BY SOMETHING but says nothing about how many it swallows. That is problem 1097's question, not this one.

## Sort one dimension away, then count the other

Swallowing asks two questions at once: is the start at or after mine, and is the end at or before mine. Sorting handles one of them and a Fenwick tree handles the other.

compress the ends to ranks 1..k sort the intervals by a, DESCENDING walk the sorted order in GROUPS of equal a: first, insert every member of the group into the tree at rank(b) then, for every member i of the group: swallowed[i] = tree.prefix(rank(b_i)) - 1

The tree counts how many inserted intervals have an end at or below b_i. Because the walk is by descending a, everything inserted has a >= a_i, so the prefix count is exactly the number of intervals j with a_j >= a_i and b_j <= b_i. Interval i itself is among them, which is what the - 1 removes.

O(n log n).

## Why the group must be inserted before it is queried

An interval with the SAME start as i and an end at or below b_i is swallowed by i and must be counted. If the group were queried one member at a time, inserting as it went, the members earlier in the group would be missing from the counts of the later ones and the answer would depend on an arbitrary order within the group.

Inserting the whole group first makes every member see every other member with the same start, which is exactly right and also makes the - 1 uniform: every interval counts itself once, whatever its group.

## Why compressing the ends is not optional

Ends reach 10^9 in magnitude, so a tree indexed by raw end would need 2 * 10^9 slots. Only n distinct ends can occur, so replacing each by its position in the sorted list of distinct ends shrinks the tree to at most 2 * 10^5 entries. Ranking preserves order, so every comparison the algorithm makes is unchanged.

## The boundary that breaks a careless implementation

Both comparisons in the definition are non-strict, so [3,4] inside [1,4] counts, and identical intervals count both ways. A solution using strict comparisons answers 0 1 on the third sample.

Ties on the count are broken by the smallest interval NUMBER, so walk the intervals in input order at the end and record a new best only on a strict improvement.

## 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. The tree's own entries are counts bounded by n. Nothing here needs 64 bits.

## Related

Problem 1097 asks how many intervals are NOT swallowed by any other, which a sort and a running maximum answer in one pass, because it needs only a yes or no per interval. Counting HOW MANY each one swallows is a two-dimensional dominance count and needs the tree. Problem 2003 uses the same tree over ranks to count inversions, which is the same counting problem with the roles of the two coordinates swapped.

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a ≤ b ≤ 10^9` - interval `i` swallows interval `j` when `a_i ≤ a_j` and `b_j ≤ b_i`, both non-strict - two intervals with the same endpoints swallow each other