二分时间+区间覆盖

解题思路:

1、对时间进行二分搜索，
2、对于每个判断的时间，可以每个阀门视为一个区间，判断由此得到区间组是否能够覆盖整个大区间
注意事项:
1、右边界需要开大一点，10的9次方不行，需要开到10的10次方

2、得到的区间一定要先排序（阀门开的时间不同，可能会出现区间交错，包含的情况）

参考代码:

def check(t):
    ls = []
    for i, (x, y) in enumerate(vle):
        if t >= y:
            ls.append((x-(t-y),x+(t-y)))    # 将阀门展开为区间
    ls.sort()
    if len(ls) == 0:
        return False
    if ls[0][0] > 1:
        return False
    r = ls[0][1]
    for i in range(1, len(ls)):             # 判断是否能够覆盖区间
        if ls[i][0]-r <= 1:
            r = max(r, ls[i][1])
        else:
            break
    return r >= lon


n, lon = map(int, input().split())
vle = []
for i in range(n):
    vle.append(list(map(int, input().split())))
l, r = 0, 10**10
while l < r:                                 # 二分搜索时间，右边界需要开大一些
    mid = (l+r)//2
    if check(mid):
        r = mid
    else:
        l = mid+1
print(l)