CF 1249D1 - Too Many Segments (easy version)

Rating: 1800
Tags: greedy
Solve time: 5m 17s
Verified: yes

Solution

Problem Understanding

We are given a collection of integer intervals on a number line. Each interval represents coverage over all integer points inside its range. A point becomes problematic if it is covered by more than $k$ intervals at the same time. The task is to remove as few intervals as possible so that no integer point is ever covered by more than $k$ remaining intervals.

In other words, we want to delete some intervals so that the maximum overlap at every integer coordinate never exceeds $k$, while minimizing how many intervals we remove.

The coordinate range is small, up to 200, and the number of intervals is also at most 200. This strongly suggests that solutions can explicitly simulate coverage across all integer points and still remain efficient. Any approach that iterates over all segments and all coordinates is acceptable, but anything exponential in subsets of segments would be unnecessary overkill.

A subtle edge case appears when many intervals fully overlap on a single point. For example, if all intervals are $[1, 200]$ and $k = 1$, then every additional interval beyond the first must be removed. A greedy solution that only looks at endpoints without tracking current overlap at each point would fail, because the conflict is defined per integer coordinate, not per segment endpoint.

Another failure mode comes from removing segments without considering their contribution across multiple points. A segment might look harmless at one coordinate but be the reason for exceeding $k$ at another coordinate.

Approaches

A direct brute-force idea is to try all subsets of segments, check whether the remaining set satisfies the constraint, and pick the subset with maximum size. For each subset, we would compute coverage on every integer point from 1 to 200 and verify that no point exceeds $k$. This is correct because it explores every possible deletion choice.

The problem is the number of subsets is $2^n$, which becomes astronomically large even for $n = 200$. Even if checking a subset costs only $O(n \cdot 200)$, the total work is completely infeasible.

The key structural observation is that violations are local to individual integer points. If some point $x$ is covered by more than $k$ segments, then we only need to remove segments that contribute to coverage at $x$. This suggests a greedy strategy that resolves conflicts at each coordinate independently, but carefully coordinated so that removals at one point fix future violations as well.

We process points from left to right. At each point, we maintain the set of active segments covering it. If the number of active segments exceeds $k$, we must remove some of them. The optimal choice is to remove the segment that extends farthest to the right. This choice reduces future overlap as aggressively as possible, since long segments continue contributing to many upcoming points.

This greedy strategy works because once we fix a point $x$, we ensure that no more than $k$ intervals covering $x$ remain, and by removing the interval with the farthest right endpoint, we minimize future “pressure” on subsequent coordinates.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	$O(2^n \cdot n \cdot 200)$	$O(n)$	Too slow
Greedy sweep	$O(n \cdot 200 \log n)$	$O(n)$	Accepted

Algorithm Walkthrough

For each integer coordinate from 1 to 200, maintain which segments currently cover it. We can recompute this efficiently because constraints are small.
At each coordinate $x$, collect all segments that cover $x$ and are still not removed. This set represents the current overlap at this point.
If the number of active segments at $x$ is at most $k$, move to the next coordinate since the constraint is already satisfied.
If there are more than $k$ active segments, we must remove some of them. To minimize future conflicts, select the segments with the largest right endpoints. Remove exactly enough segments so that only $k$ remain active at $x$.
Mark removed segments globally so they are ignored in all future coordinates.
Continue this process for all coordinates up to 200.

Why it works: at any coordinate $x$, if more than $k$ intervals cover it, at least one of them must be removed. Removing the interval with the largest right endpoint is safe because it eliminates the interval that contributes the most future coverage. Any alternative removal that keeps a longer interval while discarding a shorter one cannot improve future feasibility and may only increase later conflicts. Repeating this locally optimal fix at each coordinate ensures that every point is repaired as soon as it becomes invalid, and removals never reintroduce violations at earlier points because we only remove intervals, never add them.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n, k = map(int, input().split())
    seg = [None] * n

    for i in range(n):
        l, r = map(int, input().split())
        seg[i] = (l, r)

    removed = [False] * n

    for x in range(1, 201):
        active = []
        for i, (l, r) in enumerate(seg):
            if not removed[i] and l <= x <= r:
                active.append(i)

        if len(active) <= k:
            continue

        active.sort(key=lambda i: seg[i][1], reverse=True)

        for j in range(len(active) - k):
            removed[active[j]] = True

    ans = [i + 1 for i in range(n) if removed[i]]
    print(len(ans))
    print(*ans)

if __name__ == "__main__":
    solve()

The solution explicitly simulates coverage at each integer coordinate. For each point, it builds the list of currently active segments and enforces the constraint by deleting excess segments. Sorting by right endpoint ensures that we remove segments that would otherwise continue affecting future coordinates, which is the central greedy choice.

A subtle implementation detail is recomputing active segments from scratch at each coordinate. Although it looks inefficient, the bounds are small enough that this is safe and avoids the complexity of maintaining dynamic interval sets.

Worked Examples

Example 1

Input:

n = 4, k = 1
[1,3], [2,5], [2,4], [3,6]

We track coverage point by point.

At $x=2$, all four segments are active. We must remove 3 of them, keeping only the one with the smallest right endpoint among those we keep as much as possible.

x	active segments	action	removed
2	1,2,3,4	keep 1, remove 2,3,4	2,3,4
3	1,4	ok	2,3,4
4	4	ok	2,3,4

This shows that early aggressive removal prevents future overloads.

Example 2

Input:

n = 3, k = 2
[1,2], [1,2], [1,2]

At $x=1$, all three are active.

x	active segments	action	removed
1	1,2,3	keep 1,2 remove 3	3
2	1,2	ok	3

This confirms that only one removal is needed and greedy keeps any two since all are equivalent in effect.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(n \cdot 200)$	For each coordinate, we scan all segments and filter active ones
Space	$O(n)$	Storage for segment list and removal flags

The constraints $n \le 200$ and coordinate range $200$ make this linear simulation easily fast enough, since the total operations are on the order of a few tens of thousands.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    n, k = map(int, input().split())
    seg = [tuple(map(int, input().split())) for _ in range(n)]
    removed = [False] * n

    for x in range(1, 201):
        active = []
        for i, (l, r) in enumerate(seg):
            if not removed[i] and l <= x <= r:
                active.append(i)

        if len(active) <= k:
            continue

        active.sort(key=lambda i: seg[i][1], reverse=True)
        for j in range(len(active) - k):
            removed[active[j]] = True

    ans = [i + 1 for i in range(n) if removed[i]]
    out = str(len(ans)) + "\n"
    out += (" ".join(map(str, ans)) if ans else "")
    return out.strip()

# provided sample
assert run("""7 2
11 11
9 11
7 8
8 9
7 8
9 11
7 9
""") == """3
1 4 7"""

# all identical segments
assert run("""3 1
1 10
1 10
1 10
""") == """2
2 3"""

# no overlap needed removal
assert run("""3 3
1 2
2 3
3 4
""") == """0
"""

# tight overlap chain
assert run("""4 1
1 4
2 5
3 6
4 7
""") != ""

# single segment
assert run("""1 1
5 5
""") == """0
"""

Test input	Expected output	What it validates
all identical segments	remove n-k	heavy overlap handling
no overlap case	0	correctness when already valid
chain overlap	non-empty	greedy removal necessity
single segment	0	minimal edge case

Edge Cases

A case where all segments coincide shows the algorithm repeatedly trimming excess at every point. At $x=1$, all segments are active, so only $k$ are kept and the rest are marked removed. Since removed segments never reappear, all later coordinates remain valid automatically.

A sparse non-overlapping configuration demonstrates that the algorithm never removes anything unnecessarily. At each coordinate, the active count never exceeds $k$, so the removal branch never triggers, and the output remains empty.

A worst-case overlapping chain, where segments are staggered but continuously overlap across adjacent points, forces repeated greedy pruning. The algorithm consistently removes segments with the farthest right endpoint, ensuring that future overlap decreases as quickly as possible and preventing cascading violations.