Too Many Segments (easy version) (Codeforces 1249D1)
Tags: Greedy, greedy

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 200$$$) — 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 200$$$) — 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
1 4 7

3
1 2 4

4
1 3 5 6

Solution (Python):
(n, k) = map(int, input().split())
l = []
for _ in range(n):
    l.append(list(map(int, input().split())))
v = [0 for _ in range(n)]
for curr in range(1, 201):
    x = 0
    t = []
    for i in range(n):
        if v[i] == 0 and l[i][0] <= curr <= l[i][1]:
            x += 1
            t.append([l[i][1], l[i][0], i])
    if x > k:
        t = sorted(t)[::-1]
        for i in range(x - k):
            (b, a, index) = t[i]
            v[index] = 1
ans = sum(v)
print(ans)
ans = []
for i in range(n):
    if v[i] == 1:
        ans.append(i + 1)
print(*ans)

Solution (Python):
(n, k) = map(int, input().split(' '))
segments = [tuple(map(int, input().split(' '))) for i in range(n)]
min_point = min((i[0] for i in segments))
max_point = max((i[1] for i in segments))
removed_segments = set()
for point in range(min_point, max_point + 1):
    intersections = []
    for i in range(n):
        if segments[i][0] <= point <= segments[i][1] and i not in removed_segments:
            intersections.append(i)
    if len(intersections) > k:
        intersections.sort(key=lambda x: segments[x][1])
        removed_segments.update(intersections[k:])
print(len(removed_segments))
print(*[i + 1 for i in removed_segments])

Solution (Python):
(n, k) = map(int, input().split())
arr = []
for i in range(n):
    (l, r) = map(int, input().split())
    arr.append([r, l, i])
arr.sort()
ans = []
for i in range(201):
    s = 0
    a = []
    for j in arr:
        if i <= j[0] and i >= j[1]:
            s += 1
            if s > k:
                ans.append(j[2] + 1)
                a.append(j)
    for j in a:
        arr.remove(j)
print(len(ans))
print(*sorted(ans))