Problem p02874 (python)

Fixed submission:
N = int(input())
LR = [list(map(int,input().split())) for _ in range(N)]

LR.sort(key=lambda x:[-x[0],x[1]])
ML = LR[0][0]
MR = LR[0][1]
LR.sort(key=lambda x:[x[1],-x[0]])
mR = LR[0][1]
mL = LR[0][0]

ans = max(mR-ML+1,0)
for i in range(N):
    if LR[i] not in [[ML,MR],[mL,mR]]:
        ans = max(ans,max(mR-ML+1,0)+max(LR[i][1]-LR[i][0]+1,0))

LR.sort(key=lambda x:[x[1],x[0]])

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

for i in range(1,N):
    ans = max(ans,max(LR[i][1]-ML+1,0)+max(mR-L_[i-1]+1,0))

print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
LR = [list(map(int,input().split())) for _ in range(N)]

ML = max(LR)[0]
mR = min(LR,key=lambda x:x[1])[1]

ans = max(ML-mR+1,0)+max([LR[i][1]-LR[i][0]+1 for i in range(N)])
LR.sort(key=lambda x:[x[1],x[0]])

L_ = [0]*N
for i in range(N):
    L_[i] = max(L[i],L_[i-1])

for i in range(1,N):
    ans = max(ans,max(LR[i][1]-ML+1,0)+max(mR-L_[i-1]+1,0))

print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
LR = [list(map(int,input().split())) for _ in range(N)]


ML = max(LR)[0]
mR = min(LR,key=lambda x:x[1])[1]

ans = max(ML-mR+1,0)+max([LR[i][1]-LR[i][0]+1 for i in range(N)])
LR.sort(key=lambda x:[x[1],x[0]])

L_ = [0]*N
for i in range(N):
    L_[i] = min(L[i],L_[i-1])

for i in range(1,N):
    ans = max(ans,max(LR[i]-ML+1,0)+max(mR-L_[i-1]+1,0))

print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
LR = [list(map(int,input().split())) for _ in range(N)]

ML = max(LR)[0]
mR = min(LR,key=lambda x:x[1])[1]

if ML > mR:
    LR.sort(key=lambda x:[x[1],x[0]])
    L = [LR[i][0] for i in range(N)]
    for i in range(N):
        r = LR[i][1]
        if ML <= r:
            break

    L_ = [0]*N
    for j in range(N):
        L_[j] = max(L[j],L_[j-1])

    ans = LR[i][1]-ML+1
    for j in range(max(i,1),N):
        ans = max(ans,LR[j][1]-ML+1+max(mR-L_[j-1]+1,0))

else:
    l,r = min(LR,key=lambda x:x[1])
    LR.sort()
    R = [LR[i][1] for i in range(N)]
    for i in range(N):
        if LR[i][0] > l:
            break

    R_ = [0]*N
    R_[-1] = R[-1]
    for j in range(N-2,i-1,-1):
        R_[j] = min(R[j],R_[j+1])

    ans = mR-LR[i-1][0]+1
    for j in range(i-1,N-2):
        ans = max(ans,mR-L[j]+1+R_[j+1]-ML+1)

print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
LR = [list(map(int,input().split())) for _ in range(N)]

ML = max(LR)[0]
mR = min(LR,key=lambda x:x[1])[1]

if ML > mR:
    LR.sort(key=lambda x:[x[1],x[0]])
    L = [LR[i][0] for i in range(N)]
    for i in range(N):
        r = LR[i][1]
        if ML <= r:
            break

    L_ = [0]*N
    for j in range(N):
        L_[j] = max(L[j],L_[j-1])

    ans = LR[i][1]-ML+1
    for j in range(max(i,1),N):
        ans = max(ans,LR[j][1]-ML+1+max(mR-L_[j-1]+1,0))

else:
    l,r = min(LR,key=lambda x:x[1])
    LR.sort()
    R = [LR[i][1] for i in range(N)]
    for i in range(N):
        if LR[i][0] > l:
            break

    R_ = [0]*N
    R_[-1] = R[-1]
    for j in range(N-2,i-1,-1):
        R_[j] = min(R[j],R_[j+1])

    ans = mR-LR[i-1][0]+1
    for j in range(i-1,N-1):
        ans = max(ans,mR-L[j]+1+R_[j+1]-ML+1)

print(ans)