Survey in Class (Codeforces 1834D)
Tags: Greedy, sortings

Zinaida Viktorovna has $$$n$$$ students in her history class. The homework for today included $$$m$$$ topics, but the students had little time to prepare, so $$$i$$$-th student learned only topics from $$$l_i$$$ to $$$r_i$$$ inclusive.At the beginning of the lesson, each student holds their hand at $$$0$$$. The teacher wants to ask some topics. It goes like this:  The teacher asks the topic $$$k$$$.  If the student has learned topic $$$k$$$, then he raises his hand by $$$1$$$, otherwise he lower it by $$$1$$$. Each topic Zinaida Viktorovna can ask no more than one time.Find the maximum difference of the heights of the highest and the lowest hand that can be in class after the survey.Note that the student's hand can go below $$$0$$$.

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$$$ ($$$2 \le n \le 10^5, 1 \le m \le 10^9$$$) — the number of students and the number of topics, respectively.Each of the next $$$n$$$ lines of each test case contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$) — the endpoints of the segment of topics that $$$i$$$-th student has learned.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, print one integer — the maximum difference of the heights of the highest and the lowest hand that can be in the class after the survey.

Note: In the first test case, Zinaida Viktorovna can ask the topics $$$5, 6, 7, 8$$$. Then the hand of the $$$2$$$-nd student will be at the height of $$$4$$$, and the hand of the $$$4$$$-th will be at the height of $$$-2$$$, that is, the difference will be equal to $$$6$$$.In the second test case, you can ask about the topics $$$1$$$ and $$$3$$$. Then the hand of the $$$1$$$-st student will be at the height of $$$2$$$ and the hand of the $$$3$$$-rd student will be at the height of $$$-2$$$. So the difference will be $$$4$$$.In the third test case, the difference between the highest and lowest hand will be $$$0$$$ for any set of topics asked.In the fifth test case, you can ask all topics. Then the difference between the heights of the $$$1$$$-st and $$$3$$$-rd students' hands will be $$$12$$$.

Sample Inputs:
6
4 8
2 6
4 8
2 7
1 5
3 3
1 3
2 3
2 2
3 5
1 5
1 5
1 5
3 5
1 1
3 3
5 5
4 7
1 7
1 3
3 3
4 5
2 4
1 3
2 4

Sample Outputs:
6
4
0
2
12
2

Solution (Python):
import sys, threading, bisect, heapq, math
from functools import cmp_to_key as ctk
from collections import defaultdict, deque
readline = sys.stdin.readline
read = lambda : [int(x) for x in readline().split()]
alloc = lambda dfv, *s: len(s) != 1 and [alloc(dfv, *s[1:]) for _ in range(int(s[0]))] or [dfv] * int(s[0])
bet = lambda a, b: a <= b and range(a, b + 1) or range(a, b - 1, -1)
show = lambda arr: print(' '.join(map(str, arr)))
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    for _wzl_ in range(int(input())):
        (n, m) = read()
        arr = []
        (mxl, mnr, mnlen) = (-1, INF, INF)
        for _ in range(n):
            arr.append(read())
            mxl = max(mxl, arr[-1][0])
            mnr = min(mnr, arr[-1][1])
            mnlen = min(mnlen, arr[-1][1] - arr[-1][0] + 1)
        res = 0
        for (a, b) in arr:
            res = max(res, b - max(a - 1, mnr), min(mxl, b + 1) - a, b - a + 1 - mnlen)
        print(res * 2)
main()

Solution (Python):
import sys
input = lambda : sys.stdin.buffer.readline().decode('utf-8').rstrip('\r\n')
from array import array
inp = lambda : int(input())
mi = lambda x=int: map(x, input().split())
arr = lambda d='i', x=int: array(d, mi(x))
li = lambda x=int: list(mi(x))
lb = lambda : list(map(int, input()))
ls = lambda : list(input())
bi = lambda n: bin(n).replace('0b', '')
yn = ['No', 'Yes']
YN = ['NO', 'YES']
YY = 'YES'
NN = 'NO'
yy = 'Yes'
nn = 'No'
inf = sys.maxsize
mod = 998244353
alp = 'abcdefghijklmnopqrstuvwxyz'
from itertools import accumulate as cml, permutations
from collections import Counter as ctr, deque as dq, defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from math import ceil, gcd, log, sqrt
import heapq as hq

def main(kase):
    (n, m) = mi()
    lmx = 0
    rmn = 10000000000.0
    sml = 10000000000.0
    rn = [li() for i in range(n)]
    ans = 0
    for x in rn:
        lmx = max(lmx, x[0])
        rmn = min(rmn, x[1])
        sml = min(sml, x[1] - x[0] + 1)
    for x in rn:
        if x[0] > rmn or x[1] < lmx:
            ans = max(ans, 2 * (x[1] - x[0] + 1))
        else:
            ans = max(ans, 2 * (x[1] - x[0] + 1) - 2 * min(sml, x[1] - lmx + 1, rmn - x[0] + 1))
    print(ans)
    pass
if __name__ == '__main__':
    test_Cases = 1
    test_Cases = inp()
    for i in range(test_Cases):
        main(i)

Solution (Python):
t = int(input())
for it in range(t):
    (n, m) = map(int, input().split())
    a = []
    ot1 = -1
    k = -1
    ot2 = -1
    p = 1000000000000
    ot3 = -1
    dl = 10000000000000
    for i in range(n):
        a.append(list(map(int, input().split())))
        if a[i][1] - a[i][0] < dl:
            dl = a[i][1] - a[i][0]
            ot3 = i
        if a[i][0] > k:
            k = a[i][0]
            ot1 = i
        if a[i][1] < p:
            p = a[i][1]
            ot2 = i
    ans = 0
    for i in range(n):
        if a[ot1][0] <= a[i][1]:
            ans = max(ans, a[ot1][0] - a[i][0])
        else:
            ans = max(ans, a[i][1] - a[i][0] + 1)
        if a[ot2][1] < a[i][0]:
            ans = max(ans, a[i][1] - a[i][0] + 1)
        else:
            ans = max(ans, a[i][1] - a[ot2][1])
        if a[i][1] < a[ot3][0] or a[i][0] > a[ot3][1]:
            ans = max(ans, a[i][1] - a[i][0] + 1)
        else:
            ans = max(ans, a[i][1] - a[i][0] - (a[ot3][1] - a[ot3][0]))
    print(ans * 2)