40. Min On-Call Points Cover

Problem

Each escalation needs at least one on-call shift starting inside its window. Given a list of escalation time-windows (start, end), each of which must contain at least one chosen shift-start "point," find the minimum number of points such that every window contains at least one of them.

This is the classic greedy interval point cover problem: sort intervals by end, greedily place a point at the end of the first not-yet-covered interval, skip every interval that point already covers (start <= point <= end), and repeat. It runs in O(n log n) time, dominated by the sort.

Source: src/40_min_oncall_points_cover.py

def min_points_to_cover(intervals: list[tuple[int, int]]) -> int:

>>> min_points_to_cover([(1, 4), (2, 6), (5, 8), (7, 9)])
2
>>> min_points_to_cover([(1, 10), (2, 5), (3, 4)])
1
>>> min_points_to_cover([(1, 2), (3, 4), (5, 6)])
3

Step-by-Step Approach

1. Handle the empty-input case: no intervals means zero points are needed.
2. Sort all intervals by their end value ascending. This ordering is what makes the greedy choice provably optimal.
3. Walk through the sorted intervals, tracking the most recently placed point (initially none).
4. For each interval, check whether the current point already falls inside it (start <= last_point <= end). If so, this interval is already covered for free — skip it.
5. If the current point does not cover this interval (or no point has been placed yet), place a new point at this interval's end. Placing it as late as possible maximizes the chance that later, overlapping intervals get covered by the same point.
6. Increment the point counter each time a new point is placed.
7. Return the total number of points placed once every interval has been processed.

The key insight is an exchange argument: among all points that could cover the earliest-ending uncovered interval, choosing that interval's own end point is never worse than choosing any earlier point, because the end point covers the maximal range of any interval that could possibly overlap this one going forward — so the greedy choice never loses to an optimal solution.

Reference solution

def min_points_to_cover(intervals: list[tuple[int, int]]) -> int:
    # sort by end ascending, greedily place a point at the end of each first
    # uncovered interval -- classic exchange-argument greedy, O(n log n) time
    if not intervals:
        return 0
    # sort by end, not start
    ordered = sorted(intervals, key=lambda iv: iv[1])
    points = 0
    # sentinel: no point placed yet
    last_point = None
    # tuple unpacking
    for start, end in ordered:
        # strictly past last point = uncovered
        if last_point is None or start > last_point:
            last_point = end
            points += 1
    return points

Key Functions & Tricks

• sorted(intervals, key=lambda iv: iv[1]) — new list ordered by each tuple's end value, needed for greedy optimality.
• for start, end in ordered — tuple unpacking destructures each pair in the loop header.
• last_point = None — sentinel for "no point placed yet," distinct from any real integer point.
• start > last_point — strict inequality; a start exactly at the last point is still covered.

How to Recognize This Pattern