二分时间+区间合并

解题思路:

注意事项:

参考代码:

def sort1(m):

    a,b=m

    return b,a

def sort2(m):

    a,b=m

    return a,-b

def check(mid):

    list2=[] # 用来区间合并

    for i in list1:

        th,t=i

        if t<=mid:

            left,right=th-(mid-t),th+(mid-t)

            if left<1:

                left=1

            list2.append([left,right])

        else:

            break

    list2=sorted(list2,key=sort2)

    # 区间合并

    l,r=list2[0]

    if l!=1:

        return 0

    for i in list2[1:]:

        a,b=i

        if b<=r: # 包含

            continue

        else:

            if a-r>1:

                return 0

            else:

                # 修改

                r=b

    if r>=lens:

        return 1

    return 0

n,lens=map(int,input().split())

list1=[]

for i in range(n):

    list1.append(list(map(int,input().split())))

list1=sorted(list1,key=sort1)

# 二分时间

left=list1[0][1] # 总得有个时间

right=10**14

result=[]

while left<=right:

    mid=(left+right)>>1

    if check(mid):

        right=mid-1

        result.append(mid)

    else:

        left=mid+1

print(result[-1])