Problem:
 Score : 600 points    Problem Statement 10^9 contestants, numbered 1 to 10^9 , will compete in a competition.
There will be two contests in this competition.  The organizer prepared N problems, numbered 1 to N , to use in these contests.
When Problem i is presented in a contest, it will be solved by all contestants from Contestant L_i to Contestant R_i (inclusive), and will not be solved by any other contestants.  The organizer will use these N problems in the two contests.
Each problem must be used in exactly one of the contests, and each contest must have at least one problem.  The joyfulness of each contest is the number of contestants who will solve all the problems in the contest.
Find the maximum possible total joyfulness of the two contests.      Constraints  2 \leq N \leq 10^5  1 \leq L_i \leq R_i \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  L_1  R_1  L_2  R_2  \vdots  L_N  R_N       Output Print the maximum possible total joyfulness of the two contests.        Sample Input 1 4
4 7
1 4
5 8
2 5      Sample Output 1 6  The optimal choice is:   Use Problem 1 and 3 in the first contest. Contestant 5 , 6 , and 7 will solve both of them, so the joyfulness of this contest is 3 .  Use Problem 2 and 4 in the second contest. Contestant 2 , 3 , and 4 will solve both of them, so the joyfulness of this contest is 3 .  The total joyfulness of these two contests is 6 . We cannot make the total joyfulness greater than 6 .        Sample Input 2 4
1 20
2 19
3 18
4 17      Sample Output 2 34       Sample Input 3 10
457835016 996058008
456475528 529149798
455108441 512701454
455817105 523506955
457368248 814532746
455073228 459494089
456651538 774276744
457667152 974637457
457293701 800549465
456580262 636471526      Sample Output 3 540049931

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    LRs = []
    Ls, Rs = [], []
    for _ in range(N):
        L, R = map(int, input().split())
        LRs.append((L, R))
        Ls.append(L)
        Rs.append(R)

    Ls.sort(reverse=True)
    Rs.sort()

    maxL, maxL2 = Ls[:2]
    minR, minR2 = Rs[:2]

    
    ans = 0
    for L, R in LRs:
        num = R-L+1
        A, B = maxL, minR
        if L == maxL:
            A = maxL2
        if R == minR:
            B = minR2
        num += max(0, B-A+1)
        ans = max(ans, num)

    
    LRs.sort(key=lambda x: x[0])

    minR = LRs[0][1]
    accMinRs = [minR]
    for L, R in LRs[1:]:
        minR = min(minR, R)
        accMinRs.append(minR)
    minR = LRs[-1][1]
    accMinRRevs = [minR]
    for L, R in reversed(LRs[:-1]):
        minR = min(minR, R)
        accMinRRevs.append(minR)
    accMinRRevs = accMinRRevs[::-1]

    for i in range(N-1):
        num = max(0, accMinRs[i] - LRs[i][0] + 1)
        num += max(0, accMinRRevs[i+1] - LRs[-1][0] + 1)
        ans = max(ans, num)

    
    LRs.sort(key=lambda x: x[1])

    maxL = LRs[0][0]
    accMaxLs = [maxL]
    for L, R in LRs[1:]:
        maxL = max(maxL, L)
        accMaxLs.append(maxL)
    maxL = LRs[-1][0]
    accMaxLRevs = [maxL]
    for L, R in reversed(LRs[:-1]):
        maxL = max(maxL, L)
        accMaxLRevs.append(maxL)
    accMaxLRevs = accMaxLRevs[::-1]

    for i in range(N-1):
        num = max(0, LRs[0][1] - accMaxLs[i] + 1)
        num += max(0, LRs[i+1][1] - accMaxLRevs[i+1] + 1)
        ans = max(ans, num)

    print(ans)


solve()

Solution (Python):
import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  
rs = lambda: stdin.readline().rstrip()  

N = ri()
L = []
R = []
for _ in range(N):
    l, r = rl()
    L.append(l)
    R.append(r)

max_l = max(L)
min_R = min(R)
ab = [(max(0, r - max_l + 1), max(0, min_R - l + 1)) for l, r in zip(L, R)]
ab.sort()
answer = max(r - l + 1 for l, r in zip(L, R)) + max(0, min_R - max_l + 1)
mi = float('inf')

for i in range(N-1):
    mi = min(mi, ab[i][1])
    answer = max(answer, mi + ab[i+1][0])

print(answer)

Solution (Python):
import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  
rs = lambda: stdin.readline().rstrip()  

N = ri()
L = []
R = []

for _ in range(N):
    l, r = rl()
    L.append(l)
    R.append(r)

max_l = max(L)
min_r = min(R)
ab = [(max(0, r - max_l + 1), max(0, min_r - l + 1)) for l, r in zip(L, R)]
ab.sort()
mi = float('inf')
answer = max(r - l + 1 for l, r in zip(L, R)) + max(0, min_r - max_l + 1)
for i in range(N - 1):
    mi = min(mi, ab[i][1])
    
    answer = max(answer, mi + ab[i + 1][0])
print(answer)

Solution (Python):
def main():
    n = int(input())
    lr = [list(map(int, input().split())) for _ in [0] * n]
    lr.sort(key=lambda x: (x[0], x[1]))
    min_r = [0] * n
    min_r[0] = lr[0][1]
    min_l = [0] * n
    min_l[n-1] = lr[n-1][1]
    for i in range(1,n):
        min_r[i] = min(min_r[i - 1], lr[i][1])
    for i in range(n-2,-1,-1):
        min_l[i] = min(min_l[i + 1], lr[i][1])
    ans = max([max(min_r[i] - lr[i][0] + 1, 0) + max(min_l[i + 1] - lr[n - 1][0] + 1, 0) for i in range(n - 1)])
    l,r,w=0,10**9+1,0
    for i in range(n):
        l = max(l, lr[i][0])
        r = min(r, lr[i][1])
        w = max(w, lr[i][1] - lr[i][0]+1)
    ans = max(ans, max(r - l + 1, 0) + w)
    print(ans)
main()

Solution (Python):
def main():
  n,*t=map(int,open(0).read().split())
  (x,y),*t,(a,b)=sorted(zip(*[iter(t)]*2))
  r_min=[b]
  l_max=[a]
  for l,r in t[::-1]:
    r_min+=min(r_min[-1],r),
    l_max+=max(l_max[-1],l),
  m=max(0,y-x+1)+max(0,r_min.pop()-l_max.pop()+1)
  for l,r in t:
    i=r_min.pop()
    j=l_max.pop()
    v=min(y,r)
    w=max(x,l)
    m=max(m,max(0,i-j+1)+max(0,v-w+1),max(0,min(i,y)-max(j,x)+1)+max(0,r-l+1))
    y,x=v,w
  m=max(m,max(0,b-a+1)+max(0,y-x+1))
  print(m)
main()

Solution (Python):
def main():
  n,*t=map(int,open(0).read().split())
  (x,y),*t,(a,b)=sorted(zip(*[iter(t)]*2))
  r_min=[b]
  l_max=[a]
  for l,r in t[::-1]:
    r_min+=min(r_min[-1],r),
    l_max+=max(l_max[-1],l),
  m=max(0,y-x+1)+max(0,r_min.pop()-l_max.pop()+1)
  for l,r in t:
    i=r_min.pop()
    j=l_max.pop()
    v=min(y,r)
    w=max(x,l)
    m=max(m,max(0,i-j+1)+max(0,v-w+1),max(0,min(i,y)-max(j,x)+1)+max(0,r-l+1))
    y,x=v,w
  m=max(m,max(0,b-a+1)+max(0,y-x+1))
  print(m)
main()

Solution (Python):
def main():
    n = int(input())
    ranges = []
    ans = 0
    for i in range(n):
        l, r = map(int, input().split())
        ranges.append((l, r))
        ans = max(ans, r - l + 1)
    min_ri = (10 ** 9 + 1, -1)
    max_li = (-1, -1)
    for i, (l, r) in enumerate(ranges):
        min_ri = min(min_ri, (r, i))
        max_li = max(max_li, (l, i))
    ri = min_ri[1]
    li = max_li[1]
    subranges = [ranges[i] for i in range(n) if i != ri and i != li]
    for r in subranges:
        ans = max(ans, min_ri[0] - max_li[0] + r[1] - r[0] + 2)
    if ri != li:
        lens = []
        for l, r in subranges:
            lens.append((max(0, r - max_li[0] + 1), max(0, min_ri[0] - l + 1)))
        lens.sort(key=lambda t: (t[0], -t[1]))
        m = len(subranges)
        fs = [ranges[li][1] - ranges[li][0] + 1] * (m + 1)
        ss = [ranges[ri][1] - ranges[ri][0] + 1] * (m + 1)
        for i in range(m):
            ss[i + 1] = min(ss[i], lens[i][1])
        for i in range(m, 0, -1):
            fs[i - 1] = min(fs[i], lens[i - 1][0])
        for i in range(m + 1):
            ans = max(ans, fs[i] + ss[i])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
lr=[list(map(int,input().split())) for _ in range(n)]
lr.sort(key=lambda x:x[0])
lr.sort(key=lambda x:x[1])
mae=[]
l=0
r=10**9
for i in range(n-1):
    ll,rr=lr[i]
    l=max(ll,l)
    r=min(rr,r)
    mae.append(r-l+1)

usi=[]
l=0
r=10**9+1
for i in range(n-1,0,-1):
    ll,rr=lr[i]
    l=max(ll,l)
    r=min(rr,r)
    usi.append(r-l+1)
usi.reverse()

ans=0

for i in range(n-1):
    ans=max(mae[i]+usi[i],ans)

lr2=[(0,-1)]
ll=0
rr=10**9
for i in range(n-1):
    l,r=lr[i]
    ll=max(ll,l)
    rr=min(rr,r)
    lr2.append((ll,rr))
lr3=[(0,-1)]
ll=0
rr=10**9
for i in range(n-1,0,-1):
    l,r=lr[i]
    ll=max(ll,l)
    rr=min(rr,r)
    lr3.append((ll,rr))
lr3.reverse()

ans2=0
for i in range(n):
    l,r=lr[i]
    rr=min(lr2[i][1],lr3[i][1])
    ll=max(lr2[i][0],lr3[i][0])
    d=max(0,rr-ll+1)
    ans2=max(ans2,r-l+1+d)


ans=max(ans,ans2)



print(ans)

Solution (Python):
from sys import stdin

def main():
  N, *LR = map(int, stdin.buffer.read().split())
  L, R = LR[::2], LR[1::2]
  max_l = max(L)
  min_r = min(R)
  ab = [(max(0, r - max_l + 1), max(0, min_r - l + 1)) for l, r in zip(L, R)]
  
  
  ab.sort()
  mi = float("inf")
  ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, min_r - max_l + 1)
  
  for i in range(N - 1):
    mi = min(mi, ab[i][1])
    
    ma = max(ma, mi + ab[i + 1][0])
    
  print(ma)
    
main()

Solution (Python):



def solve(*args: str) -> str:
    n = int(args[0])
    LR = [tuple(map(int, a.split())) for a in args[1:]]

    ret = 0

    
    
    lp, rq = 0, 1+10**9
    d_max = 0
    for l, r in LR:
        lp, rq = max(lp, l), min(rq, r)
        d_max = max(d_max, 1+r-l)

    ret = max(0, 1+rq-lp) + d_max

    AB = [[max(0, 1+r-lp), max(0, 1+rq-l)] for l, r in LR]
    AB.sort(key=lambda x: (x[0], -x[1]))
    A, B = map(list, zip(*AB))

    
    
    b_min = 1+10**9
    for i in range(n-1):
        b_min = min(b_min, B[i])
        ret = max(ret, b_min + A[i+1])

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):



def solve(*args: str) -> str:
    n = int(args[0])
    LR = [tuple(map(int, a.split())) for a in args[1:]]
    L, R = zip(*LR)

    ret = 0

    
    lp, rq = 0, 1+10**9
    for l, r in LR:
        lp, rq = max(lp, l), min(rq, r)

    ret = max(0, 1+rq-lp) + max(0, max(1+r-l for l, r in LR))

    AB = [[max(0, 1+r-lp), max(0, 1+rq-l)] for l, r in LR]
    AB.sort(key=lambda x: (x[0], -x[1]))
    A, B = map(list, zip(*AB))

    
    
    b_min = 1+10**9
    for i in range(n-1):
        b_min = min(b_min, B[i])
        ret = max(ret, b_min + A[i+1])

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):

import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    LR = [tuple(map(int, a.split())) for a in args[1:]]
    L, R = zip(*LR)

    ret = 0

    p, q = np.argmax(L), np.argmin(R)
    lp, rq = L[p], R[q]

    ret = max(0, 1+rq-lp) + max(0, max(1+r-l for l, r in LR))

    AB = [[max(0, 1+r-lp), max(0, 1+rq-l)] for l, r in LR]
    AB.sort(key=lambda x: (x[0], -x[1]))
    A, B = map(list, zip(*AB))

    
    
    b_min = 1+10**9
    for i in range(n-1):
        b_min = min(b_min, B[i])
        ret = max(ret, b_min + A[i+1])

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):






from operator import itemgetter





N = int(input())
LR = [[0, 0] for _ in range(N)]
for i in range(N):
    LR[i][0], LR[i][1] = map(int, input().split())





maxL = 0
minR = 10 ** 9
for i in range(N):
    maxL = max(maxL, LR[i][0])
    minR = min(minR, LR[i][1])





ans = 0





def func(list):
    ret = []
    left = list[0][0]
    right = list[0][1]
    ret.append(right - left + 1)
    for i in range(1, len(list)):
        left = max(left, list[i][0])
        right = min(right, list[i][1])
        ret.append(right - left + 1)
    return ret





LR.sort(key=itemgetter(1))
LR.sort(key=itemgetter(0))
list1 = func(LR)
LR.reverse()
list2 = func(LR)





m = 0
for i in range(N - 1):
    m = max(m, list1[i] + list2[N - i - 2])
ans = max(ans, m)





LR.sort(key=itemgetter(1), reverse=True)
LR.sort(key=itemgetter(0))
list1 = func(LR)
LR.reverse()
list2 = func(LR)





m = 0
for i in range(N - 1):
    m = max(m, list1[i] + list2[N - i - 2])
ans = max(ans, m)





LR.sort(key=itemgetter(0))
LR.sort(key=itemgetter(1))
list1 = func(LR)
LR.reverse()
list2 = func(LR)





m = 0
for i in range(N - 1):
    m = max(m, list1[i] + list2[N - i - 2])
ans = max(ans, m)





LR.sort(key=itemgetter(0), reverse=True)
LR.sort(key=itemgetter(1))
list1 = func(LR)
LR.reverse()
list2 = func(LR)





m = 0
for i in range(N):
    m = max(m, LR[i][1] - LR[i][0] + 1)

if minR >= maxL:
    ans = max(ans, m + minR - maxL + 1)
else:
    ans = max(ans, m)





print(ans)

Solution (Python):
N = int(input())
LR = [[int(i) for i in input().split()] for _ in range(N)]

for i in range(N) :
    LR[i][1] += 1

a, b = 0, 0
la, ra = 0, float('inf')
lb, rb = -float('inf'), 0

for i, (l, r) in enumerate(LR) :
    if r < ra or (r == ra and l < la) :
        la, ra = l, r
        a = i
        
    if l > lb or (l == rb and r > rb) :
        lb, rb = l, r
        b = i

ret = 0

Md = 0
for i, (l, r) in enumerate(LR) :
    if i != a and i != b :
        Md = max(Md, r - l)
ret = max(ret, max(0, ra - lb) + Md)

LR.sort(key=lambda x: x[1])
LR.sort()
dpl = [0] * N
dpr = [0] * N

dpl[0] = max(la, LR[0][0])
dpr[N-1] = min(rb, LR[N-1][1])

for i in range(1, N) :
    dpl[i] = max(dpl[i-1], LR[i][0])
    dpr[N-1-i] = min(dpr[N-i], LR[N-1-i][1])
    
for i in range(N - 1) :
    ret = max(ret, max(0, ra - dpl[i]) + max(0, dpr[i + 1] - lb))
    
print(ret)

Solution (Python):
n = int(input())
lr = [tuple(map(int, input().split())) for _ in range(n)]

left_sort = sorted(lr, key=lambda tup: tup[0])     

joy_from_left = [0]
min_right = float('inf')
max_left = 0
for l, r in left_sort:     
    min_right = min(r, min_right)
    max_left = max(l, max_left)
    joy_from_left.append(max(0, min_right - max_left + 1))

joy_from_right = [0]
min_right = float('inf')
max_left = 0
for l, r in reversed(left_sort):       
    min_right = min(r, min_right)
    max_left = max(l, max_left)
    joy_from_right.append(max(0, min_right - max_left + 1))

joy_pair = max(l+r for l, r in zip(joy_from_left, reversed(joy_from_right)))        


longest = max(left_sort, key=lambda tup: tup[1]-tup[0])     
longest_joy = longest[1] - longest[0] + 1

removed = list(filter(lambda tup: tup!=longest, left_sort))     
min_right = min(r for _, r in removed)
max_left = max(l for l, _ in removed)
except_longest_joy = max(0, min_right - max_left + 1)

print(max(joy_pair, longest_joy + except_longest_joy))

Solution (Python):
N = int(input())
LR = []
L, R = [], []
for _ in range(N):
    l, r = map(int,  input().split())
    LR.append((l, r))
    L.append(l)
    R.append(r)
L.sort()
R.sort()
ans = 0
for l, r in LR:
    m = L[-1]
    M = R[0]
    if l == m:
        m = L[-2]
    if M == r:
        M = R[1]
    ans = max(max(0, M-m+1)+r-l+1, ans)
LR.sort()
tmp = [LR[-1]]
Rmin = LR[-1][1]
for i in range(N-1)[::-1]:
    if LR[i][1]<=Rmin:
        tmp.append(LR[i])
        Rmin = LR[i][1]
LR = tmp[::-1]
rmin = LR[0][1]
lmax = LR[-1][0]
for i in range(len(LR)-1):
    l0, r0 = LR[i]
    l1, r1 = LR[i+1]
    res1 = max(0, rmin-l0+1)
    res2 = max(0, r1-lmax+1)
    ans = max(ans, res1+res2)
print(ans)

Solution (Python):
n = int(input())
raw = []
for _ in range(n):
  raw.append(list(map(int,input().split())))
raw.sort(key= lambda x: x[1])
EF = []
for i in range(n):
  EF.append(raw[i][1])
SL1 = [raw[0][0]]
for i in range(1,n):
  SL1.append(max(SL1[-1],raw[i][0]))
SL2 = [raw[-1][0]]
for i in range(1,n):
  SL2.append(max(SL2[-1],raw[n-i-1][0]))
SL2.reverse()



can = []
for i in range(n-1):
  tmp = max(EF[0]-SL1[i]+1,0) + max(EF[i+1]-SL2[i+1]+1,0)
  can.append(tmp)

ans1 = max(can)
xlen = []
xl = []
xr = []
for i in range(n):
  xlen.append(raw[i][1] - raw[i][0] + 1)
  xl.append(raw[i][0])
  xr.append(raw[i][1])

ans2 = max(xlen) + max(0,min(xr)-max(xl)+1)
print(max(ans1,ans2))

Solution (Python):
N = int(input())
LRs = [list(map(int,input().split())) for i in range(0,N)]

L,R = zip(*LRs)
Lp = max(L)
Rq = min(R)

A = [max(0, r-Lp+1) for r in R]
B = [max(Rq-l+1, 0) for l in L]
AB = sorted(zip(A,B))
A2,B2 = zip(*AB)

mlr = max(r-l for l,r in LRs) + 1
m = max(0, Rq - Lp + 1) + mlr
mt = B2[0]
for i,a in enumerate(A2[0:-1:]):
    mt = min(mt, B2[i])
    ms = A2[i+1]
    m = max(m, ms+mt)

print(m)

Solution (Python):
def solve(N, LRs):
    from operator import itemgetter
    L = 0
    R = 1
    IND = 2

    LRs.sort(key=itemgetter(L))  
    LRs = tuple(LR + (ind,) for ind, LR in enumerate(LRs))

    min_r = min(LRs, key=itemgetter(R))  
    max_l = max(LRs, key=itemgetter(L))  

    ans = 0
    if min_r[IND] == max_l[IND]:
        
        fixed = max(0, min_r[R] - max_l[L] + 1)
        max_ = max(0, max(x[R] - x[L] + 1 for x in LRs if x[IND] != max_l[IND]))
        ans = max(ans, fixed + max_)
    else:
        

        
        fixed = max(0, min_r[R] - max_l[L] + 1)
        max_ = max(0, max(x[R] - x[L] + 1 for x in LRs if x[IND] != max_l[IND]))
        ans = max(ans, fixed + max_)

        r_mins = []
        t = 10 ** 9 + 1
        for LR in reversed(LRs):
            if LR[IND] != min_r[IND]:
                t = min(t, LR[R])
            r_mins.append(t)
        r_mins.reverse()

        
        for x in LRs:
            
            if x[IND] == max_l[IND]:
                continue
            fixed = max(0, min_r[R] - x[L] + 1)
            r_ = r_mins[x[IND] + 1]
            opp = max(0, r_ - max_l[L] + 1)
            ans = max(ans, fixed + opp)

    return ans


if __name__ == '__main__':
    N = int(input())
    LRs = [tuple(map(int, input().split())) for _ in range(N)]
    print(solve(N, LRs))

Solution (Python):
import sys
input = sys.stdin.readline

_n = int(input())
lrlist = [list(map(int, input().split())) for _ in range(_n)]
Lp, Rq = max(l for l, r in lrlist), min(r for l, r in lrlist)

st = sorted([(max(r - Lp + 1, 0), max(Rq - l + 1, 0)) for l, r in lrlist], key=lambda x: (x[0], -x[1]))
ans = max([r - l + 1 for l, r in lrlist]) + max(Rq - Lp + 1, 0)

min_b = 10 ** 9
for i in range(_n - 1):
    min_b = min(st[i][1], min_b)
    ans = max(ans, min_b + st[i + 1][0])

print(ans)

Solution (Python):
from sys import stdin

def main():
    N, *LR = map(int, stdin.buffer.read().split())
    L, R = LR[::2], LR[1::2]

    Lp = max(L)
    Rq = min(R)

    AB = sorted((max(0, r - Lp + 1), -max(0, Rq - l + 1)) for l, r in zip(L, R))

    mi = float("inf")
    ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, Rq - Lp + 1)

    for i, (a, b) in enumerate(AB):
        if i:
            ma = max(ma, mi + a)
        mi = min(mi, -b)

    print(ma)


main()

Solution (Python):
from sys import stdin

def main():
    N, *LR = map(int, stdin.buffer.read().split())
    L, R = LR[::2], LR[1::2]

    Lp = max(L)
    Rq = min(R)

    A, B = zip(*sorted((max(0, r - Lp + 1), -max(0, Rq - l + 1)) for l, r in zip(L, R)))

    mi = float("inf")
    ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, Rq - Lp + 1)

    for a, b in zip(A[1:], B):
        mi = min(mi, -b)
        ma = max(ma, mi + a)

    print(ma)


main()

Solution (Python):
N, *LR = map(int, open(0).read().split())
L, R = LR[::2], LR[1::2]

Lp = max(L)
Rq = min(R)

A, B = zip(*sorted((max(0, r - Lp + 1), -max(0, Rq - l + 1)) for l, r in zip(L, R)))

mi = float("inf")
ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, Rq - Lp + 1)

for a, b in zip(A[1:], B):
    mi = min(mi, -b)
    ma = max(ma, mi + a)

print(ma)

Solution (Python):
from sys import stdin

def main():
    N, *LR = map(int, stdin.buffer.read().split())
    L, R = LR[::2], LR[1::2]

    Lp = max(L)
    Rq = min(R)

    A = sorted(max(0, r - Lp + 1) for r in R)
    B = sorted(-max(0, Rq - l + 1) for l in L)

    mi = float("inf")
    ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, Rq - Lp + 1)

    for a, b in zip(A[1:], B):
        mi = min(mi, -b)
        ma = max(ma, mi + a)

    print(ma)

main()

Solution (Python):
N, *LR = map(int, open(0).read().split())
L, R = LR[::2], LR[1::2]

Lp = max(L)
Rq = min(R)

A = sorted(max(0, r - Lp + 1) for r in R)
B = sorted(-max(0, Rq - l + 1) for l in L)

mi = float("inf")
ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, Rq - Lp + 1)

for a, b in zip(A[1:], B):
    mi = min(mi, -b)
    ma = max(ma, mi + a)

print(ma)

Solution (Python):
N, *LR = map(int, open(0).read().split())
L, R = LR[::2], LR[1::2]

max_l = max(L)
min_r = min(R)

A = sorted(max(0, r - max_l + 1) for r in R)
B = sorted(-max(0, min_r - l + 1) for l in L)

mi = float("inf")
ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, min_r - max_l + 1)

for i in range(N - 1):
    mi = min(mi, -B[i])
    ma = max(ma, mi + A[i + 1])

print(ma)

Solution (Python):
N, *LR = map(int, open(0).read().split())
L, R = LR[::2], LR[1::2]

max_l = max(L)
min_r = min(R)

ab = [(max(0, r - max_l + 1), -max(0, min_r - l + 1)) for l, r in zip(L, R)]
ab.sort()

mi = float("inf")
ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, min_r - max_l + 1)

for i in range(N - 1):
    mi = min(mi, -ab[i][1])
    ma = max(ma, mi + ab[i + 1][0])

print(ma)

Solution (Python):
from sys import stdin

def main():
    N, *LR = map(int, stdin.buffer.read().split())
    L, R = LR[::2], LR[1::2]

    max_l = max(L)
    min_r = min(R)

    ab = [(max(0, r - max_l + 1), -max(0, min_r - l + 1)) for l, r in zip(L, R)]
    ab.sort()

    mi = float("inf")
    ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, min_r - max_l + 1)

    for (_, r), (l, _) in zip(ab, ab[1:]):
        mi = -r if mi > -r else mi
        ma = mi + l if ma < mi + l else ma

    print(ma)

main()

Solution (Python):
from sys import stdin

def main():
    N, *LR = map(int, stdin.buffer.read().split())
    L, R = LR[::2], LR[1::2]

    max_l = max(L)
    min_r = min(R)

    ab = [(max(0, r - max_l + 1), -max(0, min_r - l + 1)) for l, r in zip(L, R)]
    ab.sort()

    mi = float("inf")
    ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, min_r - max_l + 1)

    for (_, r), (l, _) in zip(ab, ab[1:]):
        mi = min(mi, -r)
        ma = max(ma, mi + l)

    print(ma)

main()

Solution (Python):
def main():
    N = int(input())
    L, R = [0] * N, [0] * N
    for i in range(N):
        L[i], R[i] = map(int, input().split())

    max_l = max(L)
    min_r = min(R)

    ab = [(max(0, r - max_l + 1), -max(0, min_r - l + 1)) for l, r in zip(L, R)]
    ab.sort()

    mi = float("inf")
    ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, min_r - max_l + 1)
    for i in range(N - 1):
        mi = min(mi, -ab[i][1])
        ma = max(ma, mi + ab[i + 1][0])

    print(ma)

main()

Solution (Python):
from sys import stdin

def main():
    input = stdin.buffer.readline

    N = int(input())
    L, R = [0] * N, [0] * N
    for i in range(N):
        L[i], R[i] = map(int, input().split())

    max_l = max(L)
    min_r = min(R)

    ab = [(max(0, r - max_l + 1), -max(0, min_r - l + 1)) for l, r in zip(L, R)]
    ab.sort()

    mi = float("inf")
    ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, min_r - max_l + 1)
    for i in range(N - 1):
        mi = min(mi, -ab[i][1])
        ma = max(ma, mi + ab[i + 1][0])

    print(ma)

main()

Solution (Python):
import sys

input = sys.stdin.readline

N = int(input())
L, R = [], []
length = []
for i in range(N):
	Li, Ri = map(int,input().split())
	L.append(Li)
	R.append(Ri)
	length.append(Ri-Li)

sindL = sorted(range(N), key=lambda k: L[k])
sindR = sorted(range(N), key=lambda k: R[k])
sind_len = sorted(range(N), key=lambda k: length[k])

indLmax = sindL[-1]
indRmin = sindR[0]

if N==2:
	ans = sum(length)+2
else:
	if indLmax==indRmin:
		ans = R[indRmin]-L[indLmax]+max(length)+2
	else:
		lenmax_ind = sind_len[-1]
		if lenmax_ind==indLmax or lenmax_ind==indRmin:
			lenmax_ind = sind_len[-2]
			if lenmax_ind==indLmax or lenmax_ind==indRmin:
				lenmax_ind = sind_len[-3]
		ans = max(0,R[indRmin]-L[indLmax]+1)+length[lenmax_ind]+1

		Qind = [0]*N
		Qind[indRmin] = 1
		ri = 1
		for li in range(0,N-1):
			QL, QR = L[sindL[li]], R[indRmin]
			Qind[sindL[li]] = 1
			while Qind[sindR[ri]]==1:
				ri += 1
			PL, PR = L[indLmax], R[sindR[ri]]

			ans = max(ans,max(0,PR-PL+1)+max(0,QR-QL+1))

print(ans)

Solution (Python):
from sys import stdin

def main():
    N, *LR = map(int, stdin.buffer.read().split())
    L, R = LR[::2], LR[1::2]

    max_l = max(L)
    min_r = min(R)

    ab = [(max(0, r - max_l + 1), -max(0, min_r - l + 1)) for l, r in zip(L, R)]
    ab.sort()

    mi = float("inf")
    ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, min_r - max_l + 1)
    for i in range(N - 1):
        mi = min(mi, -ab[i][1])
        ma = max(ma, mi + ab[i + 1][0])

    print(ma)

main()

Solution (Python):
def main():
    N, *LR = map(int, open(0).read().split())
    L, R = LR[::2], LR[1::2]

    max_l = max(L)
    min_r = min(R)

    ab = [(max(0, r - max_l + 1), -max(0, min_r - l + 1)) for l, r in zip(L, R)]
    ab.sort()

    mi = float("inf")
    ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, min_r - max_l + 1)
    for i in range(N - 1):
        mi = min(mi, -ab[i][1])
        ma = max(ma, mi + ab[i + 1][0])

    print(ma)

main()

Solution (Python):
def main():
    N, *LR = map(int, open(0).read().split())
    LR = list(zip(*[iter(LR)] * 2))

    max_l = max(l for l, _ in LR)
    min_r = min(r for _, r in LR)

    ab = [(max(0, r - max_l + 1), -max(0, min_r - l + 1)) for l, r in LR]
    ab.sort()

    mi = float("inf")
    ma = max(r - l + 1 for l, r in LR) + max(0, min_r - max_l + 1)
    for i in range(N - 1):
        mi = min(mi, -ab[i][1])
        ma = max(ma, mi + ab[i + 1][0])

    print(ma)

main()

Solution (Python):
N, *LR = map(int, open(0).read().split())
LR = list(zip(*[iter(LR)] * 2))

max_l = max(l for l, _ in LR)
min_r = min(r for _, r in LR)

ab = [(max(0, r - max_l + 1), -max(0, min_r - l + 1)) for l, r in LR]
ab.sort()

mi = float("inf")
ma = max(r - l + 1 for l, r in LR) + max(0, min_r - max_l + 1)
for i in range(N - 1):
    mi = min(mi, -ab[i][1])
    ma = max(ma, mi + ab[i + 1][0])

print(ma)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
lr_list = LIR(n)
lr_list.sort()
max_l1 = lr_list[-1][0]
min_r1 = INF


for i, (l, r) in enumerate(lr_list):
    if r < min_r1:
        min_r1 = r
        min_r_ind = i




if n == 2:
    print(lr_list[0][1] - lr_list[0][0] + 1 + lr_list[1][1] - lr_list[1][0] + 1)


else:
    max_diff = 0
    for i in range(n - 1):
        if i == min_r_ind:
            continue
        max_diff = max(max_diff, lr_list[i][1] - lr_list[i][0] + 1)

    ans = max(0, min_r1 -  max_l1 + 1) + max_diff


    min_r2 = lr_list[-1][1]
    for j in range(n - 2, -1, -1):
        if j == min_r_ind:
            continue
        max_l2 = lr_list[j][0]
        ans = max(ans, max(min_r1 - max_l2 + 1, 0) + max(min_r2 - max_l1 + 1, 0))
        min_r2 = min(min_r2, lr_list[j][1])


    max_l2 = lr_list[min_r_ind][0]
    ans = max(ans, max(min_r1 - max_l2 + 1, 0) + max(min_r2 - max_l1 + 1, 0))
    print(ans)

Solution (Python):
N=int(input())
LR=sorted([list(map(int,input().split())) for i in range(N)])
x,y,z,w=[0]*(N+1),[10**9+1]*(N+1),[0]*(N+1),[10**9+1]*(N+1)
l=0
for i in range(N):
    x[i+1],y[i+1]=max(x[i],LR[i][0]),min(y[i],LR[i][1])
    z[-i-2],w[-i-2]=max(z[-i-1],LR[-i-1][0]),min(w[-i-1],LR[-i-1][1])
    l=max(l,LR[i][1]-LR[i][0]+1)
print(max([max(0,y[-1]-x[i]+1)+max(0,w[i]-z[0]+1) for i in range(1,N)]+[l+max(0,y[-1]-z[0]+1)]))

Solution (Python):
from operator import itemgetter

N = int(input())
L = [[int(x) for x in input().split()] for _ in range(N)]


for i in range(N):
    L[i].append(L[i][1]-L[i][0])
    
L.sort()


    

la = L[0][0]
ra = L[0][1]
lb = L[1][0]
rb = L[1][1]
ans = L[-1][2]+1
for i in range(2, N):
    ta = max(0, min(ra, L[i][1])-max(la, L[i][0])+1) + rb-lb+1
    tb = max(0, min(rb, L[i][1])-max(lb, L[i][0])+1) + ra-la+1
    tc = max(0, min(ra, rb)-max(la,lb)+1) + L[i][1]-L[i][0]+1
    if max(ta, tb, tc) == ta:
        la = max(la, L[i][0])
        ra = min(ra, L[i][1])
    elif max(ta, tb, tc) == tb:
        lb = max(lb, L[i][0])
        rb = min(rb, L[i][1])
    else:
        la = max(la, lb)
        ra = min(ra, rb)
        lb = L[i][0]
        rb = L[i][1]
        
ans = max(ans, max(0, ra-la+1) + max(0, rb-lb+1))


print(ans)

Solution (Python):
import numpy as np

n = int(input())
l = []
r = []
for i in range(n):
    li, ri = map(int, input().split())
    l.append(li)
    r.append(ri+1)

arglmax = l.index(max(l))
argrmin = r.index(min(r))
num = 0
for i in range(n):
    num = max(r[i] - l[i], num)
ans1 = num + max(0, r[argrmin]-l[arglmax])

lst = [l, r]
lst = list(np.array(lst).T)
lst = sorted(lst, key=lambda x: (x[0]), reverse=True)
lst = sorted(lst, key=lambda x: (x[1]))
lst = list(np.array(lst).T)
sorted_l = list(lst[0])
sorted_r = list(lst[1])

sorted_r_minus_lmax = list(np.array(sorted_r)-l[arglmax])
mini = sorted_r_minus_lmax[n-1]
for i in range(1, n):
    mini = min(mini, sorted_r_minus_lmax[n-1-i])
    sorted_r_minus_lmax[n-1-i] = mini
rmin_minus_sorted_l = list(r[argrmin]-np.array(sorted_l))
mini = rmin_minus_sorted_l[0]
for i in range(1, n):
    mini = min(mini, rmin_minus_sorted_l[i])
    rmin_minus_sorted_l[i] = mini

ans2 = 0
for i in range(n-1):
    ai = max(0, sorted_r_minus_lmax[i+1])
    bi = max(0, rmin_minus_sorted_l[i])
    ans2 = max(ans2, ai+bi)

print(max(ans1, ans2))

Solution (Python):
import sys
from operator import itemgetter

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    inf = 10 ** 10
    n = int(input())
    lr = [list(map(int, input().split())) for _ in range(n)]
    biggest_l = max(l for l, r in lr)
    smallest_r = min(r for l, r in lr)
    mx = max(r - l + 1 for l, r in lr) + max(smallest_r - biggest_l + 1, 0)
    ab = [[max(0, r - biggest_l + 1), max(0, smallest_r - l + 1)] for l, r in lr]
    ab.sort(key=lambda x: (x[0], -x[1]))
    
    min_r = 10 ** 10
    for i in range(n - 1):
        if ab[i][1] < min_r: min_r = ab[i][1]
        cur = min_r + ab[i + 1][0]
        if cur > mx: mx = cur
    print(mx)

main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

n = int(input())
LR = [tuple(map(int, input().split())) for _ in range(n)]

def quicksort(x):
    if x==[]: return []

    smallerSorted = quicksort([a for a in x[1:] if a[0] < x[0][0] or (a[0] == x[0][0] and a[1] >= x[0][1])])
    biggerSorted = quicksort([a for a in x[1:] if a[0] > x[0][0] or (a[0] == x[0][0] and a[1] < x[0][1])])

    return(smallerSorted+[x[0]]+biggerSorted)

LR = quicksort(LR)

e = [[] for _ in range(n+2)]

ans = [0] * (n+1)
temp = 10 ** 9
i = 1
for L, R in LR:
    temp = min(temp, R)
    if L > temp:
        break
    ans[i] = temp - L + 1
    i += 1

temp = 10 ** 9
i = n - 1
L = LR[-1][0]
for x, R in reversed(LR):
    temp = min(temp, R)
    if L > temp:
        break
    ans[i] += temp - L + 1
    i -= 1

res = max(ans)
for L, R in LR:
    res = max(res, R - L + 1 + ans[0])



print(res)