Jumping Through Segments (Codeforces 1907D)
Tags: Others, binary search

Polycarp is designing a level for a game. The level consists of $$$n$$$ segments on the number line, where the $$$i$$$-th segment starts at the point with coordinate $$$l_i$$$ and ends at the point with coordinate $$$r_i$$$.The player starts the level at the point with coordinate $$$0$$$. In one move, they can move to any point that is within a distance of no more than $$$k$$$. After their $$$i$$$-th move, the player must land within the $$$i$$$-th segment, that is, at a coordinate $$$x$$$ such that $$$l_i \le x \le r_i$$$. This means:  After the first move, they must be inside the first segment (from $$$l_1$$$ to $$$r_1$$$);  After the second move, they must be inside the second segment (from $$$l_2$$$ to $$$r_2$$$);  ...  After the $$$n$$$-th move, they must be inside the $$$n$$$-th segment (from $$$l_n$$$ to $$$r_n$$$). The level is considered completed if the player reaches the $$$n$$$-th segment, following the rules described above. After some thought, Polycarp realized that it is impossible to complete the level with some values of $$$k$$$.Polycarp does not want the level to be too easy, so he asks you to determine the minimum integer $$$k$$$ with which it is possible to complete the level.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$)—the number of test cases. Descriptions of the test cases follow.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)—the number of segments in the level.The following $$$n$$$ lines.The $$$i$$$-th line contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i \le r_i \le 10^9$$$)—the boundaries of the $$$i$$$-th segment. Segments may intersect.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single integer—the minimum value of $$$k$$$ with which it is possible to complete the level.

Note: In the third example, the player can make the following moves:  Move from point $$$0$$$ to point $$$5$$$ ($$$3 \le 5 \le 8$$$);  Move from point $$$5$$$ to point $$$10$$$ ($$$10 \le 10 \le 18$$$);  Move from point $$$10$$$ to point $$$7$$$ ($$$6 \le 7 \le 11$$$). Note that for the last move, the player could have chosen not to move and still complete the level.

Sample Inputs:
4
5
1 5
3 4
5 6
8 10
0 1
3
0 2
0 1
0 3
3
3 8
10 18
6 11
4
10 20
0 5
15 17
2 2

Sample Outputs:
7
0
5
13

Solution (Python):
import sys

def play(k, segments):
    (l1, r1) = segments[0]
    for i in range(1, len(segments)):
        (l2, r2) = segments[i]
        (l1, r1) = (l1 - k, r1 + k)
        if r1 < l2 or l1 > r2:
            return False
        l1 = l2 if l2 > l1 else l1
        r1 = r2 if r2 < r1 else r1
    return True
input = sys.stdin.readline
testcases = int(input())
for _ in range(testcases):
    init = 0
    n = int(input())
    segments = []
    segments.append((0, 0))
    for _ in range(n):
        (l, r) = map(int, input().split())
        segments.append((l, r))
    (lo, hi) = (sys.maxsize, 0)
    for (l, r) in segments:
        lo = l if l < lo else lo
        hi = r if r > hi else hi
    while lo <= hi:
        k = (lo + hi) // 2
        if not play(k, segments):
            lo = k + 1
        else:
            hi = k - 1
    print(hi + 1)

Solution (Python):
from sys import stdin
from collections import Counter
from heapq import heappush, heappop
T = int(stdin.readline())
for t in range(T):
    n = int(stdin.readline())
    segments = []
    for _ in range(n):
        (l, r) = map(int, stdin.readline().rstrip().split(' '))
        segments.append((l, r))

    def intersect(x, y):
        return

    def can_make_it(k):
        (i, j) = (0, 0)
        for (l, r) in segments:
            (i, j) = (max(i - k, l), min(j + k, r))
            if i > j:
                return False
        return True
    lo = 0
    hi = max((s[1] for s in segments))
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_make_it(mid):
            hi = mid
        else:
            lo = mid + 1
    print(lo)

Solution (Python):
from collections import defaultdict
t = int(input())

def solve():
    l = []
    r = []
    n = int(input())
    for _ in range(n):
        (x, y) = [int(x) for x in input().split()]
        l.append(x)
        r.append(y)
    lm = 0
    rm = 1000000000.0
    while lm <= rm:
        mid = int((lm + rm) / 2)
        lo = 0
        ro = 0
        v = True
        for i in range(n):
            lo = max(lo - mid, l[i])
            ro = min(ro + mid, r[i])
            if lo > ro:
                v = False
                break
        if v:
            ans = mid
            rm = mid - 1
        else:
            lm = mid + 1
    return ans
for _ in range(t):
    print(solve())