Too Many Segments (hard version) (Codeforces 1249D2)
Tags: Greedy, sortings

The only difference between easy and hard versions is constraints.You are given $$$n$$$ segments on the coordinate axis $$$OX$$$. Segments can intersect, lie inside each other and even coincide. The $$$i$$$-th segment is $$$[l_i; r_i]$$$ ($$$l_i \le r_i$$$) and it covers all integer points $$$j$$$ such that $$$l_i \le j \le r_i$$$.The integer point is called bad if it is covered by strictly more than $$$k$$$ segments.Your task is to remove the minimum number of segments so that there are no bad points at all.

Input: The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — the number of segments and the maximum number of segments by which each integer point can be covered.The next $$$n$$$ lines contain segments. The $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 2 \cdot 10^5$$$) — the endpoints of the $$$i$$$-th segment.

Output: In the first line print one integer $$$m$$$ ($$$0 \le m \le n$$$) — the minimum number of segments you need to remove so that there are no bad points.In the second line print $$$m$$$ distinct integers $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i \le n$$$) — indices of segments you remove in any order. If there are multiple answers, you can print any of them.


Sample Inputs:
7 2
11 11
9 11
7 8
8 9
7 8
9 11
7 9

5 1
29 30
30 30
29 29
28 30
30 30

6 1
2 3
3 3
2 3
2 2
2 3
2 3

Sample Outputs:
3
4 6 7

3
1 4 5

4
1 3 5 6

Solution (Python):
import sys
import heapq
input_fn = lambda : sys.stdin.readline().rstrip()
MX = 2 * 10 ** 5

def main():
    (n, k) = map(int, input_fn().split())
    segments = [[] for _ in range(MX + 1)]
    count = [0] * (MX + 2)
    for idx in range(1, n + 1):
        (left, right) = map(int, input_fn().split())
        segments[left] += [(right, idx)]
        count[left] += 1
        count[right + 1] -= 1
    removed = []
    heap = []
    heapq.heapify(heap)
    for i in range(1, MX + 1):
        count[i] += count[i - 1]
        for (right, idx) in segments[i]:
            heapq.heappush(heap, (-right, idx))
        while count[i] > k:
            (popped_right, popped_idx) = heapq.heappop(heap)
            count[i] -= 1
            count[-popped_right + 1] += 1
            removed += [popped_idx]
    print(len(removed))
    print(*removed)
if __name__ == '__main__':
    main()

Solution (Python):
import heapq
(N, K) = [int(x) for x in input().split()]
h = [[] for i in range(200000)]
for i in range(N):
    (l, r) = [int(x) for x in input().split()]
    h[l - 1].append([-(r - 1), i + 1])
g = []
t = []
heapq.heapify(t)
hist = [0] * 200000
exited = 0
for l in range(200000):
    for ri in h[l]:
        heapq.heappush(t, ri)
        hist[-ri[0]] += 1
    while len(t) - exited > K:
        top = heapq.heappop(t)
        hist[-top[0]] -= 1
        g.append(top[1])
    exited += hist[l]
print(len(g))
print(*g)

Solution (Python):
import sys
import threading
from sys import stdin
from collections import defaultdict
from math import ceil, log10
from heapq import *

def gl():
    return list(map(int, stdin.readline().strip().split()))

def gi():
    return int(stdin.readline())

def gc():
    return stdin.readline()
mod = int(pow(10, 9)) + 7

def solution():
    (n, k) = gl()
    max_ = 0
    mp = defaultdict(list)
    prefix = [0] * 200002
    for i in range(n):
        (a, b) = gl()
        prefix[a] += 1
        prefix[b + 1] -= 1
        heappush(mp[a], (-b, i + 1))
    ans = []
    h = []
    for i in range(1, len(prefix)):
        prefix[i] += prefix[i - 1]
        while mp[i]:
            heappush(h, heappop(mp[i]))
        while prefix[i] > k:
            prefix[i] -= 1
            (top, j) = heappop(h)
            prefix[-top + 1] += 1
            ans.append(j)
    print(len(ans))
    print(*ans)

def main():
    solution()
if __name__ == '__main__':
    threading.stack_size(1 << 27)
    sys.setrecursionlimit(1 << 30)
    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()