098. Minimum Points to Cover Intervals

Why this mechanism works

Choose the earliest ending interval and place a point at its end. That point is as far right as possible while still covering the interval, giving it the best chance to cover later intervals. Skip intervals already containing the chosen point and repeat only when a new interval starts beyond it.

State and boundaries

point is the latest selected covering point. All processed intervals are covered; points contains the committed choices.

Protocol

1. Sort intervals by end.
2. If no point exists or the next start exceeds point, choose that interval's end.
3. Otherwise reuse the current point.
4. Return chosen points.

Visualization

[1,6], [2,8] -> choose 6
[7,12], [10,16] -> choose 12
points [6,12] cover all four

Python implementation

def cover_interval_points(intervals):
    points = []
    point = None
    for start, end in sorted(intervals, key=lambda pair: pair[1]):
        if point is None or start > point:
            point = end
            points.append(point)
    return points

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 cover_interval_points: points = []
intervals=[(10, 16), (2, 8), (1, 6), (7, 12)]; points=[]

L3 cover_interval_points: point = None
intervals=[(10, 16), (2, 8), (1, 6), (7, 12)]; points=[]; point=None

L4 <lambda>: for start, end in sorted(intervals, key=lambda pair: pair[1]):
pair=(10, 16)

L4 <lambda>: for start, end in sorted(intervals, key=lambda pair: pair[1]):
pair=(2, 8)

L4 <lambda>: for start, end in sorted(intervals, key=lambda pair: pair[1]):
pair=(1, 6)

L4 <lambda>: for start, end in sorted(intervals, key=lambda pair: pair[1]):
pair=(7, 12)

L4 cover_interval_points: for start, end in sorted(intervals, key=lambda pair: pair[1]):
intervals=[(10, 16), (2, 8), (1, 6), (7, 12)]; points=[]; point=None; start=1; end=6

L6 cover_interval_points: point = end
intervals=[(10, 16), (2, 8), (1, 6), (7, 12)]; points=[]; point=6; start=1; end=6

... 2 intermediate state changes omitted ...

L4 cover_interval_points: for start, end in sorted(intervals, key=lambda pair: pair[1]):
intervals=[(10, 16), (2, 8), (1, 6), (7, 12)]; points=[6]; point=6; start=7; end=12

L6 cover_interval_points: point = end
intervals=[(10, 16), (2, 8), (1, 6), (7, 12)]; points=[6]; point=12; start=7; end=12

L7 cover_interval_points: points.append(point)
intervals=[(10, 16), (2, 8), (1, 6), (7, 12)]; points=[6, 12]; point=12; start=7; end=12

L4 cover_interval_points: for start, end in sorted(intervals, key=lambda pair: pair[1]):
intervals=[(10, 16), (2, 8), (1, 6), (7, 12)]; points=[6, 12]; point=12; start=10; end=16

L2 cover_interval_points: points = []
intervals=[(1, 2), (2, 3)]; points=[]

L3 cover_interval_points: point = None
intervals=[(1, 2), (2, 3)]; points=[]; point=None

L4 <lambda>: for start, end in sorted(intervals, key=lambda pair: pair[1]):
pair=(1, 2)

L4 <lambda>: for start, end in sorted(intervals, key=lambda pair: pair[1]):
pair=(2, 3)

L4 cover_interval_points: for start, end in sorted(intervals, key=lambda pair: pair[1]):
intervals=[(1, 2), (2, 3)]; points=[]; point=None; start=1; end=2

L6 cover_interval_points: point = end
intervals=[(1, 2), (2, 3)]; points=[]; point=2; start=1; end=2

L7 cover_interval_points: points.append(point)
intervals=[(1, 2), (2, 3)]; points=[2]; point=2; start=1; end=2

L4 cover_interval_points: for start, end in sorted(intervals, key=lambda pair: pair[1]):
intervals=[(1, 2), (2, 3)]; points=[2]; point=2; start=2; end=3

Why the solution is correct

Any solution must hit the earliest-ending uncovered interval. Moving its chosen hit rightward to that interval's end cannot lose coverage of any remaining interval that contained the old hit, because those intervals end no earlier. Thus the greedy point is compatible with an optimum, and the argument repeats.

Time and space

O(n log n) time and O(n) sorting/output space.

Common mistakes

This kata uses closed intervals, so start==point is covered. Choosing interval starts lacks the earliest-finish exchange argument.

Reasoning card

Transfer exercise

Why does the same endpoint choice fail for half-open intervals over real coordinates? Specify a new point-domain convention before adapting it.