Delete a Segment

4000ms

262144K

Description:

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:

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:

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.

Sample Input:

Sample Output:

2
1
5

Informação

Provedor Codeforces

Código CF1285E