ABC256D - Union of Interval

考え方（いもす法）

Editorial - Tokio Marine & Nichido Fire Insurance Programming Contest 2022（AtCoder Beginner Contest 256)

ログインしている人数をいもす法で求められる．

• ログイン人数が0→1以上となるところが区間の左端
• ログイン人数が1以上→0となるところが区間の右端

となる．

回答例

N = int(input())
LR = [list(map(int, input().split())) for _ in range(N)]

num = 2 * 10 ** 5
acc = [0] * (num + 1)
for l, r in LR:
    acc[l] += 1
    acc[r] -= 1
for i in range(num):
    acc[i + 1] += acc[i]

ans = []
for i in range(num):
    x, y = acc[i], acc[i + 1]
    if x == 0 and y > 0:
        l = i + 1
    if x > 0 and y == 0:
        r = i + 1
        ans.append([l, r])

for l, r in ans:
    print(l, r)