Interval Scheduling - Learning Module

Loading content...

0/276

Interval Covering Problems

Beyond Activity Selection: The Covering Perspective

In the Activity Selection Problem, we asked: "How many non-overlapping activities can we fit?" We selected a maximum subset while avoiding conflicts. But interval scheduling encompasses a much richer family of problems—problems that ask the inverse question: instead of avoiding overlap, what if we want to ensure coverage?

Interval covering problems flip the script. Rather than selecting intervals that don't touch, we want to cover a target—either by placing points that "pierce" every interval, or by selecting intervals that together span an entire range. These problems arise constantly in practice: ensuring security cameras cover all hallways, scheduling inspections that catch every flight, or placing sensors along a pipeline to monitor every segment.

What You Will Learn

By the end of this page, you will understand the covering perspective on intervals, master the 'minimum points to pierce all intervals' problem with its greedy proof, solve the 'minimum intervals to cover a range' problem, recognize the duality between covering and packing problems, and build intuition for when greedy works in covering contexts.

The Covering Paradigm

To understand interval covering, we must first clarify what "covering" means in this context. There are two fundamental covering questions:

Type 1: Points covering intervals (Interval Stabbing)

Given a set of intervals, find the minimum number of points such that every interval contains at least one point. Each point "stabs" or "pierces" the intervals it lies within.

Type 2: Intervals covering a range (Set Cover on Intervals)

Given a set of available intervals and a target range, find the minimum number of intervals whose union covers the entire target range.

Both problems have elegant greedy solutions, but the strategies differ significantly. Let's build deep understanding of each.

Covering vs. Packing: The Duality of Interval Problems
Aspect	Packing (Activity Selection)	Covering (Interval Stabbing)
Objective	Maximize selected intervals	Minimize points/intervals used
Constraint	Selected intervals don't overlap	Every input interval must be covered
Overlap is...	Forbidden (conflict)	Required (intersections enable coverage)
Greedy metric	Sort by end time, select non-overlapping	Sort by end time, place point at end, skip covered
Typical application	Scheduling without conflicts	Inspection, surveillance, monitoring

The Mathematical Duality

There's a beautiful relationship between packing and covering. In graph theory terms, the maximum independent set (packing) and the minimum vertex cover are dual problems. For intervals, a similar relationship exists:

The maximum number of pairwise non-overlapping intervals equals the minimum number of points needed to stab all intervals in certain configurations.

This isn't always exact, but the intuition helps: if no two intervals overlap, you need one point per interval—exactly the count of selected intervals in activity selection. When intervals do overlap, shared points reduce the count below the total number of intervals.

Recognizing Covering Problems

If a problem asks for 'minimum resources to monitor/inspect/catch everything' or 'fewest intervals to span a range,' you're likely facing a covering problem. The key signal is that coverage must be complete—no gaps allowed—while the objective is minimization.

Minimum Points to Pierce All Intervals

This problem is sometimes called "Interval Stabbing" or "Minimum Hitting Set for Intervals." Given n intervals, we want the fewest points on the number line such that every interval contains at least one point.

Problem Statement (Formal)

Input: A set of n intervals I = {[s₁, e₁], [s₂, e₂], ..., [sₙ, eₙ]}

Output: A minimum-size set of points P = {p₁, p₂, ..., pₖ} such that for every interval [sᵢ, eᵢ], there exists some pⱼ ∈ P with sᵢ ≤ pⱼ ≤ eᵢ.

Example: Flight Inspections

Imagine you're an airport security inspector. Each flight has a time window during which it's at the gate (its interval). You want to schedule the minimum number of inspection times such that every flight gets inspected at least once during its gate time.

Interval Stabbing ExampleFinding minimum points to pierce all intervals

Input

Intervals: [1, 4], [2, 6], [5, 7], [6, 9], [8, 10]

Output

Minimum points: {4, 7, 10} (or {4, 6, 10}) — 3 points

Explanation

Point 4 covers [1,4] and [2,6]. Point 7 covers [5,7] and [6,9]. Point 10 covers [8,10]. No single placement of 2 points can cover all 5 intervals.

The Greedy Strategy: Place at Right Endpoints

The greedy algorithm for interval stabbing is elegantly simple:

Sort intervals by their right endpoint (end time)
Initialize an empty set of points and track the "last placed point"
Iterate through intervals in sorted order:
- If the current interval is NOT already covered (its start > last placed point):
  - Place a new point at this interval's right endpoint
  - Update last placed point
Return the set of placed points

This greedy choice—placing the point as far right as possible within the current interval—maximizes the chance that subsequent intervals will also be covered by this same point.

interval_stabbing.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def minimum_points_to_pierce(intervals: list[tuple[int, int]]) -> list[int]:
    """
    Find minimum points to pierce all intervals.
    
    Each interval [start, end] must contain at least one point.
    Returns the list of point positions.
    
    Time: O(n log n) for sorting, O(n) for single pass
    Space: O(n) for result (could be O(1) if returning count only)
    """
    if not intervals:
        return []
    
    # Sort by right endpoint (end time)
    sorted_intervals = sorted(intervals, key=lambda x: x[1])
    
    points = []
    last_point = float('-inf')  # No point placed yet
    
    for start, end in sorted_intervals:
        # If this interval is not covered by the last point
        if start > last_point:
            # Place a new point at the right endpoint
            last_point = end
            points.append(last_point)
    
    return points
 
 
def minimum_points_count(intervals: list[tuple[int, int]]) -> int:
    """Space-optimized version returning only the count."""
    if not intervals:
        return 0
    
    sorted_intervals = sorted(intervals, key=lambda x: x[1])
    count = 0
    last_point = float('-inf')
    
    for start, end in sorted_intervals:
        if start > last_point:
            last_point = end
            count += 1
    
    return count
 
 
# Example usage
intervals = [(1, 4), (2, 6), (5, 7), (6, 9), (8, 10)]
points = minimum_points_to_pierce(intervals)
print(f"Points needed: {points}")  # Output: [4, 7, 10]
print(f"Minimum count: {len(points)}")  # Output: 3

Proof of Correctness for Interval Stabbing

Why does placing points at right endpoints work? Let's prove this rigorously using the exchange argument—the same technique we've seen for other greedy problems.

Claim: The greedy algorithm produces an optimal solution (minimum number of points).

Proof Outline:

We'll show that any optimal solution OPT can be transformed into the greedy solution GREEDY without increasing the number of points. This proves |GREEDY| ≤ |OPT|, and since GREEDY is a valid solution, we have |OPT| ≤ |GREEDY|, thus |GREEDY| = |OPT|.

The Exchange Argument Structure

Consider the first interval in sorted order (smallest right endpoint). 2. Any solution must have a point that covers it. 3. Moving that point to the right endpoint never harms coverage (it stays within the first interval and potentially covers more). 4. Apply inductively to remaining intervals.

Detailed Proof:

Let intervals be sorted by right endpoint: I₁, I₂, ..., Iₙ where e₁ ≤ e₂ ≤ ... ≤ eₙ.

Step 1: First Interval Analysis

Consider interval I₁ = [s₁, e₁]. Any valid solution must have a point p such that s₁ ≤ p ≤ e₁. The greedy algorithm places its point at e₁.

If OPT has a point p < e₁ covering I₁, we can move p to e₁. This maintains coverage of I₁ (since e₁ ∈ [s₁, e₁]) and can only improve coverage of other intervals (pushing right never "exits" an interval earlier than necessary).

Step 2: Coverage Monotonicity

If point p covers interval [s, e] (meaning s ≤ p ≤ e) and we move p to a larger value p' with p ≤ p' ≤ e, then:

We still have s ≤ p' ≤ e (stays in the interval)
Any interval [s', e'] with s' ≤ p and e' ≥ p' is still covered

Since we sorted by right endpoint, all "later" intervals have eⱼ ≥ e₁. If a later interval Iⱼ was covered by a point in OPT, moving that point rightward (but not past the interval's right endpoint) maintains coverage.

Step 3: Inductive Transformation

After placing the greedy point at e₁:

Remove all intervals covered by this point (those with sⱼ ≤ e₁, which includes I₁)
Apply the same argument to the remaining intervals

At each step, OPT can be transformed to match GREEDY's choice, point by point. Since transformations never add points, |GREEDY| ≤ |OPT|.

Key Proof Insights

•Right endpoint is the 'greedy-safe' position — Placing here maximizes future interval coverage without risking the current interval.
•Sorting by end time is essential — It ensures we handle the 'most constrained' intervals first (those that end earliest).
•Exchange argument applicability — Works because moving points rightward within valid bounds never harms the solution.
•Greedy choice property holds — Each local decision (place at right endpoint) contributes to a global optimum.

Common Mistake: Placing at Left Endpoint

Placing points at the LEFT endpoint does NOT work. Consider intervals [1, 5] and [3, 4]. Placing at start of [3, 4] gives point 3, which covers both. But placing at start of [1, 5] (sorted by left endpoint, point = 1) covers only [1, 5], requiring another point for [3, 4]. The sorted-by-end-time invariant is crucial.

Minimum Intervals to Cover a Range

The second major covering problem asks: given a set of intervals and a target range [T_start, T_end], what's the minimum number of intervals whose union covers the entire target?

Problem Statement (Formal)

Input:

A target range [T_start, T_end]
A set of n intervals {[s₁, e₁], [s₂, e₂], ..., [sₙ, eₙ]}

Output: A minimum-size subset of intervals whose union contains every point in [T_start, T_end], or indication that coverage is impossible.

Example: Pipeline Monitoring

Imagine a 100-meter pipeline that needs sensor coverage. Available sensors have different coverage ranges. We want to select the fewest sensors that monitor the entire pipeline without gaps.

Interval Range Covering ExampleFinding minimum intervals to cover target [0, 10]

Input

Target: [0, 10], Intervals: [0, 3], [2, 5], [4, 7], [6, 9], [8, 10]

Output

Minimum intervals: {[0, 3], [2, 5], [4, 7], [6, 9], [8, 10]} — 5 intervals needed

Explanation

These 5 intervals chain together with overlapping coverage: [0,3] → [2,5] → [4,7] → [6,9] → [8,10]. Each overlap ensures no gap exists. Alternative: {[0, 3], [2, 7], [6, 10]} if those intervals existed would need only 3.

The Greedy Strategy: Extend Furthest

The greedy algorithm uses a "furthest reach" strategy:

Sort intervals by starting point
Initialize current position at T_start, count = 0
While current position < T_end:
- Among all intervals that start at or before current position, find the one that ends furthest
- If no such interval exists (gap!), return impossible
- Select this interval, update current position to its end, increment count
Return count (or the list of selected intervals)

The key insight: at each step, we want to advance as far as possible while maintaining coverage continuity. The interval starting earliest but reaching furthest achieves this.

range_covering.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
def min_intervals_to_cover_range(
    target_start: int, 
    target_end: int, 
    intervals: list[tuple[int, int]]
) -> list[tuple[int, int]] | None:
    """
    Find minimum intervals to cover the range [target_start, target_end].
    
    Returns list of selected intervals, or None if coverage is impossible.
    
    Strategy: Greedy by "furthest reach" at each step.
    Time: O(n log n) for sorting, O(n) for selection
    """
    if not intervals:
        return None if target_start < target_end else []
    
    # Sort by start point
    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    
    result = []
    current_end = target_start  # Coverage achieved so far
    i = 0
    n = len(sorted_intervals)
    
    while current_end < target_end:
        # Find the interval that starts at or before current_end
        # and extends the furthest
        furthest_end = current_end
        best_interval = None
        
        while i < n and sorted_intervals[i][0] <= current_end:
            start, end = sorted_intervals[i]
            if end > furthest_end:
                furthest_end = end
                best_interval = sorted_intervals[i]
            i += 1
        
        # If we couldn't extend, there's a gap
        if furthest_end == current_end:
            return None  # Impossible to cover
        
        # Select this interval
        result.append(best_interval)
        current_end = furthest_end
    
    return result
 
 
def min_intervals_count(
    target_start: int, 
    target_end: int, 
    intervals: list[tuple[int, int]]
) -> int:
    """Returns just the count, or -1 if impossible."""
    result = min_intervals_to_cover_range(target_start, target_end, intervals)
    return len(result) if result is not None else -1
 
 
# Example
target = (0, 10)
intervals = [(0, 3), (2, 5), (4, 7), (6, 9), (8, 10)]
coverage = min_intervals_to_cover_range(target[0], target[1], intervals)
 
if coverage:
    print(f"Intervals needed: {coverage}")
    print(f"Count: {len(coverage)}")
else:
    print("Coverage impossible!")

Correctness Proof for Range Covering

Why does the "furthest reach" strategy produce an optimal solution? Again, we use the exchange argument.

Claim: The greedy algorithm produces a minimum-size covering, or correctly reports impossibility.

Proof Sketch (Exchange Argument):

Consider any optimal solution OPT = {I₁*, I₂*, ..., Iₖ*} ordered by the sequence in which they cover the target range.

Step 1: First Interval

The first interval in OPT must start at or before T_start. Among all such intervals, suppose OPT chose interval I₁* with endpoint e₁*.

The greedy algorithm chooses the interval with the furthest endpoint among those starting at or before T_start. Call this G₁ with endpoint g₁.

By definition, g₁ ≥ e₁*. If we replace I₁* with G₁ in OPT, we get a solution that:

Still covers from T_start to at least e₁* (actually to g₁ ≥ e₁*)
Uses the same number of intervals
Has coverage at least as far as before

Step 2: Subsequent Intervals

After the first interval, we need to cover from g₁ (or e₁*) onward. By the same argument, the greedy choice of "furthest reach among valid starters" can replace OPT's choice without harm.

Step 3: Termination

Since greedy always reaches at least as far as OPT at each step, greedy terminates with at most as many intervals as OPT. Therefore, |GREEDY| ≤ |OPT|.

Why Sorting by Start Time?

Unlike interval stabbing (sort by end), range covering sorts by START. The reason: we iteratively extend from a current position, so we need efficient access to 'all intervals that could continue from here'—those starting at or before our current position. Sorting by start lets us sweep through candidates efficiently.

Comparing the Two Covering Problems
Aspect	Interval Stabbing	Range Covering
Input	Set of intervals	Set of intervals + target range
Output	Points that pierce all intervals	Intervals that cover the target
Sort by	End time	Start time
Greedy choice	Place point at right endpoint	Select interval with furthest reach
Key insight	Delay point placement as long as possible	Extend coverage as far as possible
Failure mode	N/A (always possible)	Gap in coverage (impossible)

Variations and Extensions

Both covering problems have important variations that appear in practice and interviews:

1. Weighted Interval Covering

What if each interval has a cost/weight, and we want to minimize total cost rather than count? This becomes harder—greedy no longer works directly, and we typically need dynamic programming or even more sophisticated algorithms.

2. K-Coverage

Instead of covering each point once, cover each point at least k times. This requires tracking "coverage depth" and changes the algorithm significantly.

3. Circular Intervals

When intervals wrap around (like hours on a clock), we may need to try different "break points" and apply the linear algorithm multiple times.

4. Minimum Intervals for K-Disjoint Coverage

Select minimum intervals such that the target is covered AND selected intervals form groups of size at most k. This introduces combinatorial constraints.

Real-World Applications

•Video Surveillance — Minimum cameras to cover all hallways (intervals = camera coverage ranges)
•Satellite Communication — Minimum ground stations to maintain continuous contact with an orbiting satellite
•Pipeline Inspection — Minimum sensor placements along a pipeline route
•Broadcasting — Minimum transmitters to cover a highway or rail line
•Shift Scheduling — Minimum workers to cover all required operating hours

When Greedy Fails: Weighted Covering

If intervals have different costs, greedy by 'furthest reach' may miss cheaper combinations. Example: Target [0, 10], Interval A = [0, 10] costs 100, Intervals B = [0, 5] and C = [5, 10] each cost 10. Greedy picks A (one interval, cost 100), but B+C (two intervals, cost 20) is cheaper. Weighted covering requires DP.

Implementation Insights and Edge Cases

When implementing covering algorithms, several subtleties require attention:

Edge Cases for Interval Stabbing:

Empty input — Return empty point set (0 points needed)
Single interval — One point at its endpoint suffices
All intervals share a common point — Only one point needed
No overlap between any pair — Need as many points as intervals
Open vs closed intervals — Must decide if endpoints are included ([a, b] vs (a, b))

Edge Cases for Range Covering:

Target is empty (start ≥ end) — Zero intervals needed
No interval starts at or before target start — Impossible
Gap in the middle — Detected when no valid extension exists
Target exactly matches one interval — One interval suffices
Floating point coordinates — Use appropriate comparison tolerance

edge_cases.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
def test_interval_stabbing_edge_cases():
    """Test edge cases for interval stabbing."""
    from interval_stabbing import minimum_points_to_pierce
    
    # Empty input
    assert minimum_points_to_pierce([]) == []
    
    # Single interval
    assert len(minimum_points_to_pierce([(5, 10)])) == 1
    
    # All intervals share point 5
    intervals = [(1, 5), (3, 7), (5, 10), (5, 8)]
    points = minimum_points_to_pierce(intervals)
    assert len(points) == 1
    assert all(s <= points[0] <= e for s, e in intervals)
    
    # No overlap - need all points
    intervals = [(1, 2), (3, 4), (5, 6), (7, 8)]
    assert len(minimum_points_to_pierce(intervals)) == 4
    
    # Complete overlap (nested intervals)
    intervals = [(1, 10), (2, 9), (3, 8), (4, 7)]
    points = minimum_points_to_pierce(intervals)
    assert len(points) == 1
    # Point must be in innermost interval [4, 7]
    assert 4 <= points[0] <= 7
 
 
def test_range_covering_edge_cases():
    """Test edge cases for range covering."""
    from range_covering import min_intervals_to_cover_range
    
    # Empty target (start >= end)
    assert min_intervals_to_cover_range(5, 5, [(1, 10)]) == []
    assert min_intervals_to_cover_range(5, 3, [(1, 10)]) == []
    
    # No interval covers start
    result = min_intervals_to_cover_range(0, 10, [(5, 15), (7, 20)])
    assert result is None  # Gap at [0, 5)
    
    # Gap in middle
    result = min_intervals_to_cover_range(0, 10, [(0, 3), (5, 10)])
    assert result is None  # Gap at (3, 5)
    
    # One interval covers exactly
    result = min_intervals_to_cover_range(0, 10, [(0, 10)])
    assert result == [(0, 10)]
    
    # Redundant intervals (more than needed)
    intervals = [(0, 5), (0, 6), (4, 10), (5, 10), (3, 10)]
    result = min_intervals_to_cover_range(0, 10, intervals)
    # Should select [0, 6] and [3, 10] or similar optimal pair
    assert len(result) == 2
 
 
if __name__ == "__main__":
    test_interval_stabbing_edge_cases()
    test_range_covering_edge_cases()
    print("All edge case tests passed!")

Debugging Covering Algorithms

When your algorithm gives wrong answers, visualize the intervals on a number line. Mark the points or selected intervals. Check: (1) Did sorting work correctly? (2) At each step, did you consider ALL valid candidates? (3) For range covering, did you update the current position correctly after each selection?

Summary: Interval Covering Mastery

Interval covering represents the "flip side" of interval selection—instead of avoiding overlap, we embrace it to achieve complete coverage. The two core problems and their greedy solutions form essential tools in your algorithm toolkit.

Key Takeaways

•Interval Stabbing (Minimum Points) — Sort by END time, place points at right endpoints, skip covered intervals. O(n log n) time.
•Range Covering (Minimum Intervals) — Sort by START time, greedily select the interval with furthest reach at each step. O(n log n) time.
•Proof technique — Both use the exchange argument, showing greedy choices can replace optimal choices without increasing cost.
•Covering vs. Packing duality — Activity selection maximizes non-overlapping count; covering minimizes resources for complete coverage.
•Weighted variants are harder — When costs differ, greedy fails; DP or other techniques required.

Coming Up Next:

We've covered the "single-resource" perspective on intervals. But what if multiple activities can occur simultaneously, each requiring its own resource? The Meeting Rooms problem asks: how many resources (rooms, platforms, processors) do we need to handle all intervals without conflict? This leads us into a new dimension of interval scheduling.

Page Complete

You now understand the covering perspective on interval scheduling. You can solve minimum point stabbing, minimum interval covering, prove these algorithms correct, and recognize when greedy applies. Next, we explore meeting room problems—determining resource requirements for overlapping intervals.

Interval Covering Problems

Beyond Activity Selection: The Covering Perspective

What You Will Learn

The Covering Paradigm

To understand interval covering, we must first clarify what "covering" means in this context. There are two fundamental covering questions:

Type 1: Points covering intervals (Interval Stabbing)

Given a set of intervals, find the minimum number of points such that every interval contains at least one point. Each point "stabs" or "pierces" the intervals it lies within.

Type 2: Intervals covering a range (Set Cover on Intervals)

Given a set of available intervals and a target range, find the minimum number of intervals whose union covers the entire target range.

Both problems have elegant greedy solutions, but the strategies differ significantly. Let's build deep understanding of each.

Covering vs. Packing: The Duality of Interval Problems
Aspect	Packing (Activity Selection)	Covering (Interval Stabbing)
Objective	Maximize selected intervals	Minimize points/intervals used
Constraint	Selected intervals don't overlap	Every input interval must be covered
Overlap is...	Forbidden (conflict)	Required (intersections enable coverage)
Greedy metric	Sort by end time, select non-overlapping	Sort by end time, place point at end, skip covered
Typical application	Scheduling without conflicts	Inspection, surveillance, monitoring

The Mathematical Duality

The maximum number of pairwise non-overlapping intervals equals the minimum number of points needed to stab all intervals in certain configurations.

Recognizing Covering Problems

Minimum Points to Pierce All Intervals

Problem Statement (Formal)

Input: A set of n intervals I = {[s₁, e₁], [s₂, e₂], ..., [sₙ, eₙ]}

Output: A minimum-size set of points P = {p₁, p₂, ..., pₖ} such that for every interval [sᵢ, eᵢ], there exists some pⱼ ∈ P with sᵢ ≤ pⱼ ≤ eᵢ.

Example: Flight Inspections

Interval Stabbing ExampleFinding minimum points to pierce all intervals

Input

Intervals: [1, 4], [2, 6], [5, 7], [6, 9], [8, 10]

Output

Minimum points: {4, 7, 10} (or {4, 6, 10}) — 3 points

Explanation

Point 4 covers [1,4] and [2,6]. Point 7 covers [5,7] and [6,9]. Point 10 covers [8,10]. No single placement of 2 points can cover all 5 intervals.

The Greedy Strategy: Place at Right Endpoints

The greedy algorithm for interval stabbing is elegantly simple:

Sort intervals by their right endpoint (end time)
Initialize an empty set of points and track the "last placed point"
Iterate through intervals in sorted order:
- If the current interval is NOT already covered (its start > last placed point):
  - Place a new point at this interval's right endpoint
  - Update last placed point
Return the set of placed points

This greedy choice—placing the point as far right as possible within the current interval—maximizes the chance that subsequent intervals will also be covered by this same point.

interval_stabbing.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def minimum_points_to_pierce(intervals: list[tuple[int, int]]) -> list[int]:
    """
    Find minimum points to pierce all intervals.
    
    Each interval [start, end] must contain at least one point.
    Returns the list of point positions.
    
    Time: O(n log n) for sorting, O(n) for single pass
    Space: O(n) for result (could be O(1) if returning count only)
    """
    if not intervals:
        return []
    
    # Sort by right endpoint (end time)
    sorted_intervals = sorted(intervals, key=lambda x: x[1])
    
    points = []
    last_point = float('-inf')  # No point placed yet
    
    for start, end in sorted_intervals:
        # If this interval is not covered by the last point
        if start > last_point:
            # Place a new point at the right endpoint
            last_point = end
            points.append(last_point)
    
    return points
 
 
def minimum_points_count(intervals: list[tuple[int, int]]) -> int:
    """Space-optimized version returning only the count."""
    if not intervals:
        return 0
    
    sorted_intervals = sorted(intervals, key=lambda x: x[1])
    count = 0
    last_point = float('-inf')
    
    for start, end in sorted_intervals:
        if start > last_point:
            last_point = end
            count += 1
    
    return count
 
 
# Example usage
intervals = [(1, 4), (2, 6), (5, 7), (6, 9), (8, 10)]
points = minimum_points_to_pierce(intervals)
print(f"Points needed: {points}")  # Output: [4, 7, 10]
print(f"Minimum count: {len(points)}")  # Output: 3

Proof of Correctness for Interval Stabbing

Why does placing points at right endpoints work? Let's prove this rigorously using the exchange argument—the same technique we've seen for other greedy problems.

Claim: The greedy algorithm produces an optimal solution (minimum number of points).

Proof Outline:

The Exchange Argument Structure

Consider the first interval in sorted order (smallest right endpoint). 2. Any solution must have a point that covers it. 3. Moving that point to the right endpoint never harms coverage (it stays within the first interval and potentially covers more). 4. Apply inductively to remaining intervals.

Detailed Proof:

Let intervals be sorted by right endpoint: I₁, I₂, ..., Iₙ where e₁ ≤ e₂ ≤ ... ≤ eₙ.

Step 1: First Interval Analysis

Consider interval I₁ = [s₁, e₁]. Any valid solution must have a point p such that s₁ ≤ p ≤ e₁. The greedy algorithm places its point at e₁.

Step 2: Coverage Monotonicity

If point p covers interval [s, e] (meaning s ≤ p ≤ e) and we move p to a larger value p' with p ≤ p' ≤ e, then:

We still have s ≤ p' ≤ e (stays in the interval)
Any interval [s', e'] with s' ≤ p and e' ≥ p' is still covered

Step 3: Inductive Transformation

After placing the greedy point at e₁:

Remove all intervals covered by this point (those with sⱼ ≤ e₁, which includes I₁)
Apply the same argument to the remaining intervals

At each step, OPT can be transformed to match GREEDY's choice, point by point. Since transformations never add points, |GREEDY| ≤ |OPT|.

Key Proof Insights

•Right endpoint is the 'greedy-safe' position — Placing here maximizes future interval coverage without risking the current interval.
•Sorting by end time is essential — It ensures we handle the 'most constrained' intervals first (those that end earliest).
•Exchange argument applicability — Works because moving points rightward within valid bounds never harms the solution.
•Greedy choice property holds — Each local decision (place at right endpoint) contributes to a global optimum.

Common Mistake: Placing at Left Endpoint

Minimum Intervals to Cover a Range

The second major covering problem asks: given a set of intervals and a target range [T_start, T_end], what's the minimum number of intervals whose union covers the entire target?

Problem Statement (Formal)

Input:

A target range [T_start, T_end]
A set of n intervals {[s₁, e₁], [s₂, e₂], ..., [sₙ, eₙ]}

Output: A minimum-size subset of intervals whose union contains every point in [T_start, T_end], or indication that coverage is impossible.

Example: Pipeline Monitoring

Imagine a 100-meter pipeline that needs sensor coverage. Available sensors have different coverage ranges. We want to select the fewest sensors that monitor the entire pipeline without gaps.

Interval Range Covering ExampleFinding minimum intervals to cover target [0, 10]

Input

Target: [0, 10], Intervals: [0, 3], [2, 5], [4, 7], [6, 9], [8, 10]

Output

Minimum intervals: {[0, 3], [2, 5], [4, 7], [6, 9], [8, 10]} — 5 intervals needed

Explanation

The Greedy Strategy: Extend Furthest

The greedy algorithm uses a "furthest reach" strategy:

Sort intervals by starting point
Initialize current position at T_start, count = 0
While current position < T_end:
- Among all intervals that start at or before current position, find the one that ends furthest
- If no such interval exists (gap!), return impossible
- Select this interval, update current position to its end, increment count
Return count (or the list of selected intervals)

The key insight: at each step, we want to advance as far as possible while maintaining coverage continuity. The interval starting earliest but reaching furthest achieves this.

range_covering.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
def min_intervals_to_cover_range(
    target_start: int, 
    target_end: int, 
    intervals: list[tuple[int, int]]
) -> list[tuple[int, int]] | None:
    """
    Find minimum intervals to cover the range [target_start, target_end].
    
    Returns list of selected intervals, or None if coverage is impossible.
    
    Strategy: Greedy by "furthest reach" at each step.
    Time: O(n log n) for sorting, O(n) for selection
    """
    if not intervals:
        return None if target_start < target_end else []
    
    # Sort by start point
    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    
    result = []
    current_end = target_start  # Coverage achieved so far
    i = 0
    n = len(sorted_intervals)
    
    while current_end < target_end:
        # Find the interval that starts at or before current_end
        # and extends the furthest
        furthest_end = current_end
        best_interval = None
        
        while i < n and sorted_intervals[i][0] <= current_end:
            start, end = sorted_intervals[i]
            if end > furthest_end:
                furthest_end = end
                best_interval = sorted_intervals[i]
            i += 1
        
        # If we couldn't extend, there's a gap
        if furthest_end == current_end:
            return None  # Impossible to cover
        
        # Select this interval
        result.append(best_interval)
        current_end = furthest_end
    
    return result
 
 
def min_intervals_count(
    target_start: int, 
    target_end: int, 
    intervals: list[tuple[int, int]]
) -> int:
    """Returns just the count, or -1 if impossible."""
    result = min_intervals_to_cover_range(target_start, target_end, intervals)
    return len(result) if result is not None else -1
 
 
# Example
target = (0, 10)
intervals = [(0, 3), (2, 5), (4, 7), (6, 9), (8, 10)]
coverage = min_intervals_to_cover_range(target[0], target[1], intervals)
 
if coverage:
    print(f"Intervals needed: {coverage}")
    print(f"Count: {len(coverage)}")
else:
    print("Coverage impossible!")

Correctness Proof for Range Covering

Why does the "furthest reach" strategy produce an optimal solution? Again, we use the exchange argument.

Claim: The greedy algorithm produces a minimum-size covering, or correctly reports impossibility.

Proof Sketch (Exchange Argument):

Consider any optimal solution OPT = {I₁*, I₂*, ..., Iₖ*} ordered by the sequence in which they cover the target range.

Step 1: First Interval

The first interval in OPT must start at or before T_start. Among all such intervals, suppose OPT chose interval I₁* with endpoint e₁*.

The greedy algorithm chooses the interval with the furthest endpoint among those starting at or before T_start. Call this G₁ with endpoint g₁.

By definition, g₁ ≥ e₁*. If we replace I₁* with G₁ in OPT, we get a solution that:

Still covers from T_start to at least e₁* (actually to g₁ ≥ e₁*)
Uses the same number of intervals
Has coverage at least as far as before

Step 2: Subsequent Intervals

After the first interval, we need to cover from g₁ (or e₁*) onward. By the same argument, the greedy choice of "furthest reach among valid starters" can replace OPT's choice without harm.

Step 3: Termination

Since greedy always reaches at least as far as OPT at each step, greedy terminates with at most as many intervals as OPT. Therefore, |GREEDY| ≤ |OPT|.

Why Sorting by Start Time?

Comparing the Two Covering Problems
Aspect	Interval Stabbing	Range Covering
Input	Set of intervals	Set of intervals + target range
Output	Points that pierce all intervals	Intervals that cover the target
Sort by	End time	Start time
Greedy choice	Place point at right endpoint	Select interval with furthest reach
Key insight	Delay point placement as long as possible	Extend coverage as far as possible
Failure mode	N/A (always possible)	Gap in coverage (impossible)

Variations and Extensions

Both covering problems have important variations that appear in practice and interviews:

1. Weighted Interval Covering

2. K-Coverage

Instead of covering each point once, cover each point at least k times. This requires tracking "coverage depth" and changes the algorithm significantly.

3. Circular Intervals

When intervals wrap around (like hours on a clock), we may need to try different "break points" and apply the linear algorithm multiple times.

4. Minimum Intervals for K-Disjoint Coverage

Select minimum intervals such that the target is covered AND selected intervals form groups of size at most k. This introduces combinatorial constraints.

Real-World Applications

•Video Surveillance — Minimum cameras to cover all hallways (intervals = camera coverage ranges)
•Satellite Communication — Minimum ground stations to maintain continuous contact with an orbiting satellite
•Pipeline Inspection — Minimum sensor placements along a pipeline route
•Broadcasting — Minimum transmitters to cover a highway or rail line
•Shift Scheduling — Minimum workers to cover all required operating hours

When Greedy Fails: Weighted Covering

Implementation Insights and Edge Cases

When implementing covering algorithms, several subtleties require attention:

Edge Cases for Interval Stabbing:

Empty input — Return empty point set (0 points needed)
Single interval — One point at its endpoint suffices
All intervals share a common point — Only one point needed
No overlap between any pair — Need as many points as intervals
Open vs closed intervals — Must decide if endpoints are included ([a, b] vs (a, b))

Edge Cases for Range Covering:

Target is empty (start ≥ end) — Zero intervals needed
No interval starts at or before target start — Impossible
Gap in the middle — Detected when no valid extension exists
Target exactly matches one interval — One interval suffices
Floating point coordinates — Use appropriate comparison tolerance

edge_cases.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
def test_interval_stabbing_edge_cases():
    """Test edge cases for interval stabbing."""
    from interval_stabbing import minimum_points_to_pierce
    
    # Empty input
    assert minimum_points_to_pierce([]) == []
    
    # Single interval
    assert len(minimum_points_to_pierce([(5, 10)])) == 1
    
    # All intervals share point 5
    intervals = [(1, 5), (3, 7), (5, 10), (5, 8)]
    points = minimum_points_to_pierce(intervals)
    assert len(points) == 1
    assert all(s <= points[0] <= e for s, e in intervals)
    
    # No overlap - need all points
    intervals = [(1, 2), (3, 4), (5, 6), (7, 8)]
    assert len(minimum_points_to_pierce(intervals)) == 4
    
    # Complete overlap (nested intervals)
    intervals = [(1, 10), (2, 9), (3, 8), (4, 7)]
    points = minimum_points_to_pierce(intervals)
    assert len(points) == 1
    # Point must be in innermost interval [4, 7]
    assert 4 <= points[0] <= 7
 
 
def test_range_covering_edge_cases():
    """Test edge cases for range covering."""
    from range_covering import min_intervals_to_cover_range
    
    # Empty target (start >= end)
    assert min_intervals_to_cover_range(5, 5, [(1, 10)]) == []
    assert min_intervals_to_cover_range(5, 3, [(1, 10)]) == []
    
    # No interval covers start
    result = min_intervals_to_cover_range(0, 10, [(5, 15), (7, 20)])
    assert result is None  # Gap at [0, 5)
    
    # Gap in middle
    result = min_intervals_to_cover_range(0, 10, [(0, 3), (5, 10)])
    assert result is None  # Gap at (3, 5)
    
    # One interval covers exactly
    result = min_intervals_to_cover_range(0, 10, [(0, 10)])
    assert result == [(0, 10)]
    
    # Redundant intervals (more than needed)
    intervals = [(0, 5), (0, 6), (4, 10), (5, 10), (3, 10)]
    result = min_intervals_to_cover_range(0, 10, intervals)
    # Should select [0, 6] and [3, 10] or similar optimal pair
    assert len(result) == 2
 
 
if __name__ == "__main__":
    test_interval_stabbing_edge_cases()
    test_range_covering_edge_cases()
    print("All edge case tests passed!")

Debugging Covering Algorithms

Summary: Interval Covering Mastery

Key Takeaways

•Interval Stabbing (Minimum Points) — Sort by END time, place points at right endpoints, skip covered intervals. O(n log n) time.
•Range Covering (Minimum Intervals) — Sort by START time, greedily select the interval with furthest reach at each step. O(n log n) time.
•Proof technique — Both use the exchange argument, showing greedy choices can replace optimal choices without increasing cost.
•Covering vs. Packing duality — Activity selection maximizes non-overlapping count; covering minimizes resources for complete coverage.
•Weighted variants are harder — When costs differ, greedy fails; DP or other techniques required.

Coming Up Next:

Page Complete