Delete a Segment
Contest: Codeforces Round 613 (Div. 2)
Difficulty rating: 2300
Tags: brute force, constructive algorithms, data structures, dp, graphs, sortings, trees, two pointers

There are $$$n$$$ segments on a $$$Ox$$$ axis $$$[l_1, r_1]$$$, $$$[l_2, r_2]$$$, ..., $$$[l_n, r_n]$$$. Segment $$$[l, r]$$$ covers all points from $$$l$$$ to $$$r$$$ inclusive, so all $$$x$$$ such that $$$l \le x \le r$$$.

Segments can be placed arbitrarily  — be inside each other, coincide and so on. Segments can degenerate into points, that is $$$l_i=r_i$$$ is possible.

Union of the set of segments is such a set of segments which covers exactly the same set of points as the original set. For example:

- if $$$n=3$$$ and there are segments $$$[3, 6]$$$, $$$[100, 100]$$$, $$$[5, 8]$$$ then their union is $$$2$$$ segments: $$$[3, 8]$$$ and $$$[100, 100]$$$;
- if $$$n=5$$$ and there are segments $$$[1, 2]$$$, $$$[2, 3]$$$, $$$[4, 5]$$$, $$$[4, 6]$$$, $$$[6, 6]$$$ then their union is $$$2$$$ segments: $$$[1, 3]$$$ and $$$[4, 6]$$$.

Obviously, a union is a set of pairwise non-intersecting segments.

You are asked to erase exactly one segment of the given $$$n$$$ so that the number of segments in the union of the rest $$$n-1$$$ segments is maximum possible.

For example, if $$$n=4$$$ and there are segments $$$[1, 4]$$$, $$$[2, 3]$$$, $$$[3, 6]$$$, $$$[5, 7]$$$, then:

- erasing the first segment will lead to $$$[2, 3]$$$, $$$[3, 6]$$$, $$$[5, 7]$$$ remaining, which have $$$1$$$ segment in their union;
- erasing the second segment will lead to $$$[1, 4]$$$, $$$[3, 6]$$$, $$$[5, 7]$$$ remaining, which have $$$1$$$ segment in their union;
- erasing the third segment will lead to $$$[1, 4]$$$, $$$[2, 3]$$$, $$$[5, 7]$$$ remaining, which have $$$2$$$ segments in their union;
- erasing the fourth segment will lead to $$$[1, 4]$$$, $$$[2, 3]$$$, $$$[3, 6]$$$ remaining, which have $$$1$$$ segment in their union.

Thus, you are required to erase the third segment to get answer $$$2$$$.

Write a program that will find the maximum number of segments in the union of $$$n-1$$$ segments if you erase any of the given $$$n$$$ segments.

Note that if there are multiple equal segments in the given set, then you can erase only one of them anyway. So the set after erasing will have exactly $$$n-1$$$ segments.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test. Then the descriptions of $$$t$$$ test cases follow.

The first of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2\cdot10^5$$$) — the number of segments in the given set. Then $$$n$$$ lines follow, each contains a description of a segment — a pair of integers $$$l_i$$$, $$$r_i$$$ ($$$-10^9 \le l_i \le r_i \le 10^9$$$), where $$$l_i$$$ and $$$r_i$$$ are the coordinates of the left and right borders of the $$$i$$$-th segment, respectively.

The segments are given in an arbitrary order.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output format:
Print $$$t$$$ integers — the answers to the $$$t$$$ given test cases in the order of input. The answer is the maximum number of segments in the union of $$$n-1$$$ segments if you erase any of the given $$$n$$$ segments.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
3
4
1 4
2 3
3 6
5 7
3
5 5
5 5
5 5
6
3 3
1 1
5 5
1 5
2 2
4 4

Example output:
2
1
5

Editorial:
Ok, looking for a new number of segments in a union is actually hard. Let $$$nw_i$$$ be the union of segments after erasing the $$$i$$$-th one. Obviously, each of the segments in $$$nw[i]$$$ has its left and right borders. Let me show you how to calculate the number of any of these two kinds. Let's choose left borders. I will call the set of left borders of the set $$$s$$$ of segments $$$lf_s$$$.
Build the initial union of all segments (that is a standart algorithm, google it if you want). Call it $$$init$$$. We are asked to find $$$\max \limits_{i} |nw[i]|$$$, but let's instead find $$$\max \limits_{i} |nw[i]| - |init|$$$ (that is the difference of sizes of the initial union and the new one for $$$i$$$). Surely, adding $$$|init|$$$ to this value will be the answer. Moreover, $$$\max \limits_{i} |nw[i]| - |init| = \max \limits_{i} |lf_{nw[i]}| - |lf_{init}|$$$ and that's what we are going to calculate. Call that difference $$$diff_i$$$.
Let's do the following sweep line. Add queries of form $$$(l_i, i, 1)$$$ and $$$(r_i, i, -1)$$$. Process them in sorted order. Maintain the set of the open segments. This sweepline will add segment $$$i$$$ on a query of the first type and remove segment $$$i$$$ on a query of the second type. Initialize all the $$$diff_i$$$ with zeroes, this sweepline will help us to calculate all the values altogether.
Look at the all updates on the same coordinate $$$x$$$. The only case we care about is: the current set of open segments contain exactly one segment and there is at least one adding update. Let this currently open segment be $$$j$$$. Consider what happens with $$$nw[j]$$$. $$$x$$$ is not in the $$$lf_{init}$$$ because at least that segment $$$j$$$ covers it. $$$x$$$ is also in $$$lf_{nf[j]}$$$ because after erasing segment $$$j$$$ $$$x$$$ becomes a left border of some segment of the union (you are adding a segment with the left border $$$x$$$ and points slightly to the left of $$$x$$$ are no longer covered by segment $$$j$$$). Thus, $$$diff_j$$$ increases by $$$1$$$.
The other possible cases are:
• there are no open segments currently — this is not important because $$$x$$$ was a left border and stays as a left border;
• there are more than two open segments — not important because $$$x$$$ will still be covered by at least one of them after erasing some other;
• there are no adding updates — $$$x$$$ was a left border but doesn't become a new one.
Thus, we handled all the left border count increasing cases. But there are also a decreasing case. Left border can get removed if the segment you are erasing had its left border in the initial union and was the only segment with such left border. You can get $$$lf_{init}$$$ while getting $$$init$$$. Then for each of $$$lf_{init}$$$ you can count how many segments start in it. Finally, iterate over $$$i$$$ and decrease $$$diff_i$$$ by one if the value for the left border of the segment $$$i$$$ is exactly $$$1$$$.
Finally, $$$diff_i$$$ is obtained, $$$(\max \limits_i diff_i) + |init|$$$ is the answer.
Overall complexity: $$$O(n \log n)$$$.