Problem p02874 (python)

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

    LRs.sort(key=itemgetter(L))  # L昇順ソート
    LRs = tuple(LR + (ind,) for ind, LR in enumerate(LRs))

    min_r = min(LRs, key=itemgetter(R))  # R最小の区間 == 右端が一番左の区間
    max_l = max(LRs, key=itemgetter(L))  # L最大の区間 == 左端が一番右の区間

    ans = 0
    if min_r[IND] == max_l[IND]:
        # L最大とR最小の問題が一致する場合
        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:
        # L最大とR最小の問題が異なる場合

        # 両方の問題を同日実施する場合
        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:
            # min_rと同日に実施する問題で、L最大の問題x
            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))

# 残った区間
# <-->, <--->
# <>は、いずれかの区間の左右端なので、n通り**4ある
# 右端が一番左にあるような区間に注目すると
# どの区間と組み合わせても、右端は変わらない（emptyになることはある）
# 右端が一番左 / 左端が一番右 に注目する

# 例外 == 両者一致 == 含まれるケース
# <----->
#  <--->
#   <->    ... この区間を含むとこの区間だけになるので、最長区間とそれ以外(これを含む）に分ける

# 右端が一番左 / 左端が一番右 を同じ区間に入れる場合と違う区間に入れる場合に分ける
# 同じ区間に入れる場合は、例外同様、最長区間とその他に分ける

# 右端が一番左 / 左端が一番右 を別日に実施する場合、
# x---o (右端は固定）
# xに決めたとき、 o---y yを最長になるようにしたい
# x---o (右端は固定）
# <---            xより左に左端があるもの : 別グループ（左端が一番右の区間以下確定）に入れると、
#                                     区間長維持または減少なので、x----oと同じグループに入れて、別グループの長さを維持したい
#       <---     oより右に左端があるもの : 別グループに入れないとx---o区間を取るという決め方に反する

Buggy submission (verdict: Runtime Error):
# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()

# int(input())
# map(int, input().split())

# 2回のコンテストに問題を分ける、一回だけ出題
# すべての問題を解く参加者の人数の和を最大化

from time import perf_counter


def solve(n, e, time_counter):
    from operator import itemgetter
    e.sort(key=itemgetter(2, 0))
    # print(e)

    ans = 0

    min_ = set()
    for j in range(n):
        if e[j][2] == e[0][2]:
            min_.add(j)
        else:
            break

    max_ = set()
    for j in range(n - 1, -1, -1):
        if e[j][2] == e[-1][2]:
            max_.add(j)
        else:
            break

    for mx in max_:
        for mn in min_:
            if mx == mn:
                continue
            if perf_counter() - time_counter == 1.8:
                print(ans)
                exit()

            ll, lr, area_l = e[mx]  # 最大
            rl, rr, area_r = e[mn]  # 最小

            for i in range(n):
                if i in (mx, mn):
                    continue
                l, r, _ = e[i]

                sr = max(0, (rr - rl + 1))
                mr = max(0, (min(rr, r) - max(rl, l) + 1))
                diff_r = sr - mr

                sl = max(0, (lr - ll + 1))
                ml = max(0, (min(lr, r) - max(ll, l) + 1))
                diff_l = sl - ml

                if diff_r < diff_l:
                    rl = max(rl, l)
                    rr = min(rr, r)
                else:
                    ll = max(ll, l)
                    lr = min(lr, r)

            ans = max(ans, max(0, (lr - ll + 1)) + max(0, (rr - rl + 1)))
    print(ans)


if __name__ == '__main__':
    import sys

    time_counter = perf_counter()

    input = sys.stdin.readline
    n = int(input().rstrip())
    e = []
    for _ in range(n):
        lr = tuple(int(x) - 1 for x in input().rstrip().split())
        lr = lr + (lr[1] - lr[0] + 1,)
        e.append(lr)
    solve(n, e, time_counter)