Doremy's Drying Plan (Easy Version) (Codeforces 1890E1)
Tags: DP, data structures

The only differences between the two versions of this problem are the constraint on $$$k$$$, the time limit and the memory limit. You can make hacks only if all versions of the problem are solved.Doremy lives in a rainy country consisting of $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$.The weather broadcast predicted the distribution of rain in the next $$$m$$$ days. In the $$$i$$$-th day, it will rain in the cities in the interval $$$[l_i, r_i]$$$. A city is called dry if it will never rain in that city in the next $$$m$$$ days.It turns out that Doremy has a special power. She can choose $$$k$$$ days (in the easy version, $$$k = 2$$$), and during these days it will not rain. Doremy wants to calculate the maximum number of dry cities after using the special power.

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. The description of the test cases follows.The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$2 \le m \le 2\cdot 10^5$$$, $$$k = 2$$$) — the number of cities, the number of days, and the number of days of rain that Doremy can prevent.Then, $$$m$$$ lines follow. The $$$i$$$-th line contains two integers $$$l_i$$$, $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — the rain coverage on day $$$i$$$.It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2\cdot 10^5$$$.

Output: For each test case, output one integer — the maximum number of dry cities.

Note: In the first test case, if Doremy prevents  rain $$$1,2$$$, then city $$$2$$$ will be dry;  rain $$$2,3$$$, then no city will be dry;  rain $$$1,3$$$, then no city will be dry; So there is at most $$$1$$$ dry city.In the second test case, if Doremy prevents  rain $$$1,2$$$, then city $$$1,2$$$ will be dry;  rain $$$2,3$$$, then city $$$4,5$$$ will be dry;  rain $$$1,3$$$, then city $$$1,5$$$ will be dry. So there are at most $$$2$$$ dry cities.In the third test case, it is optimal to prevent rain $$$2,5$$$.In the forth test case, there is always $$$4$$$ days of rain that wets all the cities and cannot be prevented.

Sample Inputs:
6
2 3 2
1 2
1 2
1 1
5 3 2
1 3
2 4
3 5
10 6 2
1 5
6 10
2 2
3 7
5 8
1 4
100 6 2
1 100
1 100
1 100
1 100
1 100
1 100
1000 2 2
1 1
1 1
20 5 2
9 20
3 3
10 11
11 13
6 18

Sample Outputs:
1
2
3
0
1000
15

Solution (Python):
import io, os
import bisect
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
    (n, m, k) = map(int, input().split())
    segs = []
    dp = [0] * (n + 1)
    for _ in range(m):
        (l, r) = map(int, input().split())
        l -= 1
        r -= 1
        dp[l] += 1
        dp[r + 1] -= 1
        segs.append((l, r))
    possible = []
    base = 0
    for i in range(n):
        if i > 0:
            dp[i] += dp[i - 1]
        if dp[i] == 0:
            base += 1
        elif dp[i] <= 2:
            possible.append(i)
    p = len(possible)
    condition = [[] for _ in range(p)]
    choices = []
    for (i, (l, r)) in enumerate(segs):
        locl = bisect.bisect_left(possible, l)
        locr = bisect.bisect(possible, r)
        for j in range(locl, locr):
            condition[j].append(i)
        if locr > locl:
            choices.append(i)
    single = {}
    double = {}
    for ele in condition:
        if len(ele) == 1:
            if ele[0] not in single:
                single[ele[0]] = 0
            single[ele[0]] += 1
        else:
            if tuple(ele) not in double:
                double[tuple(ele)] = 0
            double[tuple(ele)] += 1
    sdata = []
    for key in single:
        sdata.append(single[key])
    sdata.sort()
    ans = base
    if len(sdata) > 0:
        ans += sdata[-1]
    if len(sdata) > 1:
        ans += sdata[-2]
    for key in double:
        curr = double[key] + base
        if key[0] in single:
            curr += single[key[0]]
        if key[1] in single:
            curr += single[key[1]]
        ans = max(ans, curr)
    print(ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
import sys
ipt = sys.stdin.readline
from collections import defaultdict

def iin():
    return int(ipt())

def lmin():
    return list(map(int, ipt().split()))
for _ in range(iin()):
    (N, M, K) = lmin()
    S = set()
    E = [[] for _ in range(N + 1)]
    for i in range(M):
        (l, r) = lmin()
        E[l - 1].append(i)
        E[r].append(~i)
    ans = 0
    d = defaultdict(int)
    S = set()
    cnt = 0
    sm = [0] * M
    for i in range(N):
        for e in E[i]:
            if e >= 0:
                S.add(e)
                cnt += 1
            else:
                S.remove(~e)
                cnt -= 1
        if cnt == 0:
            ans += 1
        elif cnt == 1:
            sm[list(S)[0]] += 1
        elif cnt == 2:
            d[tuple(sorted(S))] += 1
    ma = ans + sum(sorted(sm)[-2:])
    for (k, v) in d.items():
        (i, j) = k
        ma = max(ma, ans + v + sm[i] + sm[j])
    print(ma)

Solution (Python):
import sys
import heapq
from collections import *

def solute():
    starts = defaultdict(list)
    ends = defaultdict(list)
    (n, m, k) = map(int, sys.stdin.readline().split())
    for i in range(m):
        (l, r) = map(int, sys.stdin.readline().split())
        starts[l].append(i)
        ends[r + 1].append(i)
    if m == 2:
        return n
    res = 0
    curr = set()
    ones = defaultdict(int)
    twos = defaultdict(int)
    for t in range(1, n + 1):
        for i in starts[t]:
            curr.add(i)
        for i in ends[t]:
            curr.discard(i)
        if len(curr) == 0:
            res += 1
        elif len(curr) == 1:
            ones[tuple(curr)] += 1
        elif len(curr) == 2:
            twos[tuple(sorted(curr))] += 1
    new_ones = defaultdict(int)
    for (k, v) in ones.items():
        new_ones[k[0]] = v
    add = 0
    for (k, v) in twos.items():
        curr = v
        (i, j) = tuple(k)
        curr += new_ones[i] + new_ones[j]
        if curr > add:
            add = curr
    if new_ones:
        curr = sum(sorted(new_ones.values(), reverse=True)[:2])
        if curr > add:
            add = curr
    return res + add
t = int(sys.stdin.readline())
for _ in range(t):
    print(solute())