Points Movement (Codeforces 1566F)
Tags: Greedy, sortings

There are $$$n$$$ points and $$$m$$$ segments on the coordinate line. The initial coordinate of the $$$i$$$-th point is $$$a_i$$$. The endpoints of the $$$j$$$-th segment are $$$l_j$$$ and $$$r_j$$$ — left and right endpoints, respectively.You can move the points. In one move you can move any point from its current coordinate $$$x$$$ to the coordinate $$$x - 1$$$ or the coordinate $$$x + 1$$$. The cost of this move is $$$1$$$.You should move the points in such a way that each segment is visited by at least one point. A point visits the segment $$$[l, r]$$$ if there is a moment when its coordinate was on the segment $$$[l, r]$$$ (including endpoints).You should find the minimal possible total cost of all moves such that all segments are visited.

Input: The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of points and segments respectively.The next line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the initial coordinates of the points.Each of the next $$$m$$$ lines contains two integers $$$l_j$$$, $$$r_j$$$ ($$$-10^9 \le l_j \le r_j \le 10^9$$$) — the left and the right endpoints of the $$$j$$$-th segment.It's guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case print a single integer — the minimal total cost of all moves such that all segments are visited.

Note: In the first test case the points can be moved as follows:  Move the second point from the coordinate $$$6$$$ to the coordinate $$$5$$$.  Move the third point from the coordinate $$$14$$$ to the coordinate $$$13$$$.  Move the fourth point from the coordinate $$$18$$$ to the coordinate $$$17$$$.  Move the third point from the coordinate $$$13$$$ to the coordinate $$$12$$$.  Move the fourth point from the coordinate $$$17$$$ to the coordinate $$$16$$$. The total cost of moves is $$$5$$$. It is easy to see, that all segments are visited by these movements. For example, the tenth segment ($$$[7, 13]$$$) is visited after the second move by the third point.Here is the image that describes the first test case:  

Sample Inputs:
2
4 11
2 6 14 18
0 3
4 5
11 15
3 5
10 13
16 16
1 4
8 12
17 19
7 13
14 19
4 12
-9 -16 12 3
-20 -18
-14 -13
-10 -7
-3 -1
0 4
6 11
7 9
8 10
13 15
14 18
16 17
18 19

Sample Outputs:
5
22

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right

def main():
    (n, m) = map(int, input().split())
    alst = list(map(int, input().split()))
    alst.sort()
    lr = []
    for _ in range(m):
        (l, r) = map(int, input().split())
        if bisect_left(alst, l) == bisect_right(alst, r):
            lr.append((l, r))
    alst = [-10 ** 20] + alst + [10 ** 20]
    inf = 10 ** 20
    dp = [[inf, inf] for _ in range(n + 2)]
    dp[0] = [0, 0]
    p = 0
    lr.sort()
    l = len(lr)
    for (i, a) in enumerate(alst[1:], 1):
        lst = []
        while p < l and lr[p][0] < a:
            lst.append(lr[p])
            p += 1
        if not lst:
            dp[i][0] = min(dp[i - 1])
            dp[i][1] = min(dp[i - 1])
            continue
        min_ = [alst[i]]
        for (_, r) in lst[::-1]:
            min_.append(min(min_[-1], r))
        min_ = min_[::-1]
        l_s = [alst[i - 1]] + [ll for (ll, _) in lst]
        a0 = alst[i - 1]
        a1 = alst[i]
        for (ll, m) in zip(l_s, min_):
            dp[i][0] = min(dp[i][0], dp[i - 1][0] + ll - a0 + (a1 - m) * 2, dp[i - 1][1] + (ll - a0) * 2 + (a1 - m) * 2)
            dp[i][1] = min(dp[i][1], dp[i - 1][0] + ll - a0 + a1 - m, dp[i - 1][1] + (ll - a0) * 2 + a1 - m)
    print(min(dp[-1]))
for _ in range(int(input())):
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    alst = sorted(list(map(int, input().split())))
    lr = []
    for _ in range(m):
        (l, r) = map(int, input().split())
        if bisect_left(alst, l) == bisect_right(alst, r):
            lr.append((l, r))
    alst = [-10 ** 20] + alst + [10 ** 20]
    inf = 10 ** 20
    dp = [[inf, inf] for _ in range(n + 2)]
    dp[0] = [0, 0]
    p = 0
    lr.sort()
    l = len(lr)
    for (i, a) in enumerate(alst[1:], 1):
        lst = []
        while p < l and lr[p][0] < a:
            lst.append(lr[p])
            p += 1
        if not lst:
            dp[i][0] = min(dp[i - 1])
            dp[i][1] = min(dp[i - 1])
            continue
        min_ = [alst[i]]
        for (_, r) in lst[::-1]:
            min_.append(min(min_[-1], r))
        min_ = min_[::-1]
        l_s = [alst[i - 1]] + [ll for (ll, _) in lst]
        a0 = alst[i - 1]
        a1 = alst[i]
        for (ll, m) in zip(l_s, min_):
            dp[i][0] = min(dp[i][0], dp[i - 1][0] + ll - a0 + (a1 - m) * 2, dp[i - 1][1] + (ll - a0) * 2 + (a1 - m) * 2)
            dp[i][1] = min(dp[i][1], dp[i - 1][0] + ll - a0 + a1 - m, dp[i - 1][1] + (ll - a0) * 2 + a1 - m)
    print(min(dp[-1]))

Solution (Python):
from bisect import bisect_left, bisect_right
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    alst = sorted(list(map(int, input().split())))
    lr = []
    for _ in range(m):
        (l, r) = map(int, input().split())
        if bisect_left(alst, l) == bisect_right(alst, r):
            lr.append((l, r))
    alst = [-10 ** 20] + alst + [10 ** 20]
    inf = 10 ** 20
    dp = [[inf, inf] for _ in range(n + 2)]
    dp[0] = [0, 0]
    p = 0
    lr.sort()
    l = len(lr)
    for (i, a) in enumerate(alst[1:], 1):
        lst = []
        while p < l and lr[p][0] < a:
            lst.append(lr[p])
            p += 1
        if not lst:
            dp[i][0] = min(dp[i - 1])
            dp[i][1] = min(dp[i - 1])
            continue
        min_ = [alst[i]]
        for (_, r) in lst[::-1]:
            min_.append(min(min_[-1], r))
        min_ = min_[::-1]
        l_s = [alst[i - 1]] + [ll for (ll, _) in lst]
        a0 = alst[i - 1]
        a1 = alst[i]
        for (ll, m) in zip(l_s, min_):
            dp[i][0] = min(dp[i][0], dp[i - 1][0] + ll - a0 + (a1 - m) * 2, dp[i - 1][1] + (ll - a0) * 2 + (a1 - m) * 2)
            dp[i][1] = min(dp[i][1], dp[i - 1][0] + ll - a0 + a1 - m, dp[i - 1][1] + (ll - a0) * 2 + a1 - m)
    print(min(dp[-1]))