Medium Design (Codeforces 1884C)
Tags: Greedy, sortings

The array $$$a_1, a_2, \ldots, a_m$$$ is initially filled with zeroes. You are given $$$n$$$ pairwise distinct segments $$$1 \le l_i \le r_i \le m$$$. You have to select an arbitrary subset of these segments (in particular, you may select an empty set). Next, you do the following:  For each $$$i = 1, 2, \ldots, n$$$, if the segment $$$(l_i, r_i)$$$ has been selected to the subset, then for each index $$$l_i \le j \le r_i$$$ you increase $$$a_j$$$ by $$$1$$$ (i. e. $$$a_j$$$ is replaced by $$$a_j + 1$$$). If the segment $$$(l_i, r_i)$$$ has not been selected, the array does not change.  Next (after processing all values of $$$i = 1, 2, \ldots, n$$$), you compute $$$\max(a)$$$ as the maximum value among all elements of $$$a$$$. Analogously, compute $$$\min(a)$$$ as the minimum value.  Finally, the cost of the selected subset of segments is declared as $$$\max(a) - \min(a)$$$.Please, find the maximum cost among all subsets of segments.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 10^9$$$) — the number of segments and the length of the array.The following $$$n$$$ lines of each test case describe the segments. The $$$i$$$-th of these lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$). It is guaranteed that the segments are pairwise distinct.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output the maximum cost among all subsets of the given set of segments.

Note: In the first test case, there is only one segment available. If we do not select it, then the array will be $$$a = [0, 0, 0]$$$, and the cost of such (empty) subset of segments will be $$$0$$$. If, however, we select the only segment, the array will be $$$a = [0, 1, 0]$$$, and the cost will be $$$1 - 0 = 1$$$.In the second test case, we can select all the segments: the array will be $$$a = [0, 1, 2, 3, 2, 1, 0, 0]$$$ in this case. The cost will be $$$3 - 0 = 3$$$.

Sample Inputs:
6
1 3
2 2
3 8
2 4
3 5
4 6
6 3
1 1
1 2
1 3
2 2
2 3
3 3
7 6
2 2
1 6
1 2
5 6
1 5
4 4
3 6
6 27
6 26
5 17
2 3
20 21
1 22
12 24
4 1000000000
2 999999999
3 1000000000
123456789 987654321
9274 123456789

Sample Outputs:
1
3
2
3
4
4

Solution (Python):
import math
import os
import random
import re
import sys
from collections import defaultdict
from functools import lru_cache

def solute():
    (n, m) = map(int, sys.stdin.readline().strip().split())
    d = defaultdict(int)
    d1 = defaultdict(int)
    d2 = defaultdict(int)
    d[1] = 0
    d[m] = 0
    for _ in range(n):
        (l, r) = map(int, sys.stdin.readline().strip().split())
        d[l] += 1
        if l == 1:
            d1[r + 1] += 1
        if r != m:
            d[r + 1] -= 1
        else:
            d2[l] += 1
    curr = 0
    (left, right) = (0, 0)
    MAX = 0
    for n in sorted(d.keys()):
        curr += d[n]
        if n == 1:
            left += d[n]
        left -= d1[n]
        right += d2[n]
        MAX = max(MAX, curr - min(left, right))
    return MAX
t = int(sys.stdin.readline())
for _ in range(t):
    print(solute())

Solution (Python):
for t in range(int(input())):
    (n, m) = map(int, input().split())
    (a, b, c, d, e) = ([], 0, 0, 0, 0)
    for i in range(n):
        (j, k) = map(int, input().split())
        a.append((j - 1, k))
        a.append((k, j - 1))
    for (i, j) in sorted(a):
        if i < j:
            b += 1
        else:
            b -= 1
        if i == 0:
            c += 1
        if j == 0:
            c -= 1
        if j == m:
            d += 1
        if i == m:
            d -= 1
        e = max(b - min(c, d), e)
    print(e)

Solution (Python):
t = int(input())
for _ in range(t):
    (n, m) = map(int, input().split())
    ranges = [(0, 0)] * n
    for i in range(n):
        (l, r) = map(int, input().split())
        ranges[i] = (l, r)
    events = []
    for i in range(n):
        events.append((ranges[i][0], 0, ranges[i][1]))
        events.append((ranges[i][1], 1, ranges[i][0]))
    events = sorted(events)
    freq_1 = 0
    freq_m = 0
    curr_freq = 0
    res = 0
    for event in events:
        if event[1]:
            freq_1 -= event[2] == 1
            freq_m -= event[0] == m
            curr_freq -= 1
        else:
            freq_1 += event[0] == 1
            freq_m += event[2] == m
            curr_freq += 1
        res = max(res, curr_freq - min(freq_m, freq_1))
    print(res)