Delete a Segment (Codeforces 1285E)
Tags: Others, trees

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 Inputs:
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

Sample Outputs:
2
1
5

Solution (Python):
from sys import stdin
input = stdin.buffer.readline
t = int(input())
while t:
    t -= 1
    n = int(input())
    seg = []
    for i in range(n):
        (l, r) = map(int, input().split())
        seg.append((l, 0, i))
        seg.append((r, 1, i))
    seg.sort()
    ans = 0
    seq = []
    active = set()
    increase = [0] * -~n
    for (pos, p, i) in seg:
        if p == 0:
            if len(seq) > 1 and seq[-2:] == [2, 1]:
                increase[next(iter(active))] += 1
            active.add(i)
        else:
            active.remove(i)
            if len(active) == 0:
                ans += 1
        seq.append(len(active))
    if max(seq) == 1:
        print(ans - 1)
    else:
        print(ans + max(increase))

Solution (Python):
from sys import stdin
input = stdin.buffer.readline
t = int(input())
while t:
    t -= 1
    n = int(input())
    seg = []
    for i in range(n):
        (l, r) = map(int, input().split())
        seg.append((l, 0, i))
        seg.append((r, 1, i))
    seg.sort()
    ans = 0
    seq = []
    active = set()
    increase = [0] * -~n
    for (pos, p, i) in seg:
        if p == 0:
            if len(seq) > 1 and seq[-2:] == [2, 1]:
                increase[next(iter(active))] += 1
            active.add(i)
        else:
            active.remove(i)
            if len(active) == 0:
                ans += 1
        seq.append(len(active))
    if max(seq) == 1:
        print(ans - 1)
    else:
        print(ans + max(increase))

Solution (Python):
from sys import stdin
input = stdin.buffer.readline
t = int(input())
while t:
    t -= 1
    n = int(input())
    seg = []
    for i in range(n):
        (l, r) = map(int, input().split())
        seg.append((l, 0, i))
        seg.append((r, 1, i))
    seg.sort()
    ans = 0
    seq = []
    active = set()
    increase = [0] * -~n
    for (pos, p, i) in seg:
        if p == 0:
            if len(seq) > 1 and seq[-2:] == [2, 1]:
                increase[next(iter(active))] += 1
            active.add(i)
        else:
            active.remove(i)
            if len(active) == 0:
                ans += 1
        seq.append(len(active))
    if max(seq) == 1:
        print(ans - 1)
    else:
        print(ans + max(increase))