Interval Scheduling: Minimum Meeting Rooms & Point Covering

1. Introduction and Motivation

Interval-scheduling problems all start from the same raw material: a list of intervals, each with a start and an end. What differs is the question asked about them. Can you select a maximum set of mutually non-overlapping intervals? How many resources — rooms, servers, machines — are needed to host every interval at once, at the busiest moment? What is the smallest number of marker points such that every interval contains at least one marker? Each question has a genuinely different optimal-substructure shape, and each is solved by a greedy strategy that looks superficially similar — sort something, sweep left to right — but is safe for a different reason.

Part 16 of this curriculum already proved two members of this family correct: Activity Selection, which finds the maximum number of non-overlapping intervals by sorting on end time, and the closely related Maximum Non-Overlapping Intervals problem (LeetCode's erase_overlap_intervals), which asks the complementary question — the fewest intervals to remove so what remains never overlaps. Both are solved by the same sort-by-end-time greedy and share the same exchange-argument proof; this lesson does not re-derive them.

This lesson covers the two genuinely new members of the family that Part 16 introduced only conceptually: Minimum Meeting Rooms (also called Interval Partitioning), which asks how many simultaneous "slots" the intervals require at their busiest instant, and Interval Covering (minimum points to stab every interval), which asks for the fewest points that touch every interval. Neither reduces to "pick the largest non-overlapping subset" — meeting rooms is a counting problem about simultaneous overlap, and interval covering is a hitting-set problem — so each earns its own core insight and its own correctness argument.

2. Prerequisites

This lesson assumes you can sort a list of (start, end) pairs, use a binary min-heap (or your language's priority queue), and read an exchange-argument proof. Two pieces of the interval-scheduling family are treated here as already mastered rather than material to re-learn:

• Activity Selection & the Exchange Argument (Part 16, section 4) proves — with a full exchange argument — that sorting by end time and always keeping the earliest-finishing compatible activity yields the maximum non-overlapping subset. The proof pattern used there (assume an optimal solution disagrees with greedy at the earliest point of disagreement, show the swap is safe, induct to the end) is the pattern this lesson leans on rather than repeats.
• Interval Scheduling (Part 16, section 6, the erase_overlap_intervals function) is the complementary framing of the same sort-by-end greedy: instead of counting how many intervals you can keep, it counts the minimum number you must remove to eliminate every overlap.

If you have not read those two sections, do so before continuing — the correctness reasoning in this lesson assumes you already trust that proof and builds on top of it rather than repeating it. You do not need graph algorithms, dynamic programming, or amortized analysis here; a min-heap and a comparison sort are enough.

3. A Concrete Example

flowchart TD
    A["Sort by start time:
M1(1,5) M2(2,7) M3(4,6) M4(6,8) M5(8,9)"] --> B["Process M1(1,5)
heap empty -> allocate
heap={5}  rooms=1"]
    B --> C["Process M2(2,7)
start 2 < min-end 5 -> allocate
heap={5,7}  rooms=2"]
    C --> D["Process M3(4,6)
start 4 < min-end 5 -> allocate
heap={5,6,7}  rooms=3"]
    D --> E["Process M4(6,8)
start 6 >= min-end 5 -> reuse
pop 5, push 8
heap={6,7,8}  rooms=3"]
    E --> F["Process M5(8,9)
start 8 >= min-end 6 -> reuse
pop 6, push 9
heap={7,8,9}  rooms=3"]
    F --> G["Heap size never shrank.
Peak = final size = 3 rooms"]
                

4. Minimum Meeting Rooms (Interval Partitioning)

Given $n$ meeting intervals, find the minimum number of rooms required so that no two meetings assigned to the same room overlap. This is also called interval partitioning: partition the intervals into the fewest groups such that no two intervals in the same group overlap.

A naive method scans every possible time instant between the earliest start and the latest end, and at each instant counts how many meetings are active by checking all $n$ of them. That costs roughly $O(n \cdot T)$ where $T$ is the size of the time range, and it does not even work when times are real-valued rather than a small bounded integer range. What actually matters is not every instant, but only the $O(n)$ instants where the active count can change — a meeting start or a meeting end.

Plain-English Steps

1. Sort meetings by start time, ascending.
2. Push the first meeting's end time onto an empty min-heap.
3. For each remaining meeting, in order: if its start time is at or after the heap's minimum end time, pop that minimum (its room is now free).
4. Push the current meeting's end time onto the heap (occupying either the just-freed room or a brand-new one).
5. After processing every meeting, the heap's size is the minimum number of rooms needed.

Pseudocode

min_meeting_rooms(meetings):
    sort meetings by start time ascending
    heap = empty min-heap
    push(heap, meetings[0].end)
    for each meeting in meetings[1 .. n-1]:
        if meeting.start >= peek_min(heap):
            pop_min(heap)              # earliest-freed room becomes available
        push(heap, meeting.end)        # occupy a room until this meeting ends
    return size(heap)

The full min-heap implementation below reproduces the worked-example trace above and returns 3.

import heapq

def min_meeting_rooms(meetings):
    """
    Minimum Meeting Rooms (Interval Partitioning)
    meetings: list of (start, end) tuples, end exclusive
    Time: O(n log n), Space: O(n) for the heap
    """
    if not meetings:
        return 0
    meetings = sorted(meetings, key=lambda m: m[0])
    room_ends = []  # min-heap of end times of occupied rooms
    heapq.heappush(room_ends, meetings[0][1])

    for start, end in meetings[1:]:
        if start >= room_ends[0]:
            heapq.heappop(room_ends)  # earliest-freed room becomes available
        heapq.heappush(room_ends, end)

    return len(room_ends)

# Worked example: five meetings, peak overlap of 3
meetings = [(1, 5), (2, 7), (4, 6), (6, 8), (8, 9)]
print("Minimum rooms needed:", min_meeting_rooms(meetings))  # 3

// Minimum Meeting Rooms (Interval Partitioning)
// Time: O(n log n), Space: O(n) for the heap
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

int minMeetingRooms(std::vector<std::pair<int, int>> meetings) {
    if (meetings.empty()) return 0;
    std::sort(meetings.begin(), meetings.end());  // sorts by start, then end

    std::priority_queue<int, std::vector<int>, std::greater<int>> roomEnds;
    roomEnds.push(meetings[0].second);

    for (std::size_t i = 1; i < meetings.size(); ++i) {
        if (meetings[i].first >= roomEnds.top()) {
            roomEnds.pop();  // earliest-freed room becomes available
        }
        roomEnds.push(meetings[i].second);
    }
    return static_cast<int>(roomEnds.size());
}

int main() {
    std::vector<std::pair<int, int>> meetings{{1, 5}, {2, 7}, {4, 6}, {6, 8}, {8, 9}};
    std::cout << "Minimum rooms needed: " << minMeetingRooms(meetings) << '\n';  // 3
}

// Minimum Meeting Rooms (Interval Partitioning)
// Time: O(n log n), Space: O(n) for the heap
import java.util.*;

public class MinMeetingRooms {
    static int minMeetingRooms(int[][] meetings) {
        if (meetings.length == 0) return 0;
        int[][] sorted = meetings.clone();
        Arrays.sort(sorted, (a, b) -> a[0] - b[0]);

        PriorityQueue<Integer> roomEnds = new PriorityQueue<>();  // min-heap
        roomEnds.add(sorted[0][1]);

        for (int i = 1; i < sorted.length; i++) {
            if (sorted[i][0] >= roomEnds.peek()) {
                roomEnds.poll();  // earliest-freed room becomes available
            }
            roomEnds.add(sorted[i][1]);
        }
        return roomEnds.size();
    }

    public static void main(String[] args) {
        int[][] meetings = {{1, 5}, {2, 7}, {4, 6}, {6, 8}, {8, 9}};
        System.out.println("Minimum rooms needed: " + minMeetingRooms(meetings)); // 3
    }
}

Alternative: The Sweep-Line Count

An equivalent, non-heap way to find the same answer: record a $+1$ event at every meeting's start and a $-1$ event at every meeting's end, sort all $2n$ events by time, and scan through summing the running total. The running total at any instant is exactly the number of meetings alive at that instant, so its maximum over the whole sweep is the minimum room count. The only subtlety is tie-breaking: when a meeting ends at exactly the same instant another starts, the end event must be processed first, since a room freed at time $t$ is immediately reusable by a meeting starting at $t$ — sorting ties with $-1$ before $+1$ achieves this automatically.

def min_meeting_rooms_sweep(meetings):
    """
    Sweep-line alternative: +1 at every start, -1 at every end.
    Ties sort end-before-start, since a room freed at time t is
    immediately reusable by a meeting starting at t.
    Time: O(n log n), Space: O(n) for the event list
    """
    events = []
    for start, end in meetings:
        events.append((start, 1))
        events.append((end, -1))
    events.sort()  # (-1) sorts before (+1) at an equal time

    rooms = 0
    peak = 0
    for _, delta in events:
        rooms += delta
        peak = max(peak, rooms)
    return peak

meetings = [(1, 5), (2, 7), (4, 6), (6, 8), (8, 9)]
print("Minimum rooms needed (sweep line):", min_meeting_rooms_sweep(meetings))  # 3

5. Interval Covering (Minimum Points to Stab All Intervals)

Given $n$ closed intervals on a line, find the minimum number of points such that every interval contains at least one chosen point — equivalently, "stab" or "pierce" every interval using as few needles as possible.

A brute-force method could try every subset of candidate points — only interval endpoints are ever worth trying, since sliding a point strictly inside an interval without crossing another endpoint never changes which intervals it covers — and keep the smallest subset that covers everything. But checking all subsets of endpoints is exponential. A method is needed that builds the answer one point at a time and never has to reconsider a placement.

Plain-English Steps

1. Sort intervals by end time, ascending.
2. Initialize last_point to "none placed yet."
3. For each interval in order: if its start is greater than last_point (not yet covered), place a new point at this interval's end and update last_point to that end.
4. Otherwise the interval's start is at or before last_point, so it already contains the most recently placed point — skip it, no new point needed.
5. Return the list of placed points; its length is the minimum count.

Pseudocode

min_points_to_cover(intervals):
    sort intervals by end time ascending
    points = []
    last_point = NONE
    for start, end in intervals:
        if last_point is NONE or start > last_point:
            last_point = end
            points.append(last_point)
    return points

Manual Trace

Intervals (already sorted by end): (1,3), (2,5), (4,6), (6,8), (9,12).

Result: 3 points, {3, 6, 12}, cover all five intervals. This is minimal — (1,3) and (4,6) share no common point (3 < 4), so the first four intervals alone already need at least 2 points, and (9,12) shares no point with any of them, forcing a third.

def min_points_to_cover(intervals):
    """
    Interval Covering: minimum points to stab every closed interval
    intervals: list of (start, end) tuples, both endpoints inclusive
    Time: O(n log n), Space: O(k) for the k returned points
    """
    if not intervals:
        return []
    intervals = sorted(intervals, key=lambda iv: iv[1])

    points = []
    last_point = None
    for start, end in intervals:
        if last_point is None or start > last_point:
            last_point = end
            points.append(last_point)
    return points

intervals = [(1, 3), (2, 5), (4, 6), (6, 8), (9, 12)]
result = min_points_to_cover(intervals)
print("Points placed:", result)               # [3, 6, 12]
print("Minimum points needed:", len(result))  # 3

// Interval Covering: minimum points to stab every closed interval
// Time: O(n log n), Space: O(k) for the k returned points
#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> minPointsToCover(std::vector<std::pair<int, int>> intervals) {
    std::vector<int> points;
    if (intervals.empty()) return points;
    std::sort(intervals.begin(), intervals.end(),
              [](const auto& a, const auto& b) { return a.second < b.second; });

    bool havePoint = false;
    int lastPoint = 0;
    for (const auto& iv : intervals) {
        int start = iv.first, end = iv.second;
        if (!havePoint || start > lastPoint) {
            lastPoint = end;
            havePoint = true;
            points.push_back(lastPoint);
        }
    }
    return points;
}

int main() {
    std::vector<std::pair<int, int>> intervals{{1, 3}, {2, 5}, {4, 6}, {6, 8}, {9, 12}};
    auto points = minPointsToCover(intervals);
    std::cout << "Minimum points needed: " << points.size() << '\n';  // 3
    for (int p : points) std::cout << p << ' ';                        // 3 6 12
    std::cout << '\n';
}

// Interval Covering: minimum points to stab every closed interval
// Time: O(n log n), Space: O(k) for the k returned points
import java.util.*;

public class IntervalCovering {
    static List<Integer> minPointsToCover(int[][] intervals) {
        List<Integer> points = new ArrayList<>();
        if (intervals.length == 0) return points;
        int[][] sorted = intervals.clone();
        Arrays.sort(sorted, (a, b) -> a[1] - b[1]);

        Integer lastPoint = null;
        for (int[] iv : sorted) {
            int start = iv[0], end = iv[1];
            if (lastPoint == null || start > lastPoint) {
                lastPoint = end;
                points.add(lastPoint);
            }
        }
        return points;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {2, 5}, {4, 6}, {6, 8}, {9, 12}};
        List<Integer> points = minPointsToCover(intervals);
        System.out.println("Minimum points needed: " + points.size()); // 3
        System.out.println("Points: " + points);                       // [3, 6, 12]
    }
}

Correctness (exchange argument). Consider the first interval, in end-time order, that is not yet covered when greedy is about to place its next point; greedy places that point at this interval's own end, call it $e$. Any optimal solution must also place some point inside this interval — say at position $p \le e$ — otherwise the interval would be left uncovered. Every not-yet-covered interval that $p$ covers has start $\le p \le e$, and because intervals are processed in increasing end-time order, that interval's own end is $\ge e$ — so it contains $e$ too (its start is $\le e$ and its end is $\ge e$). Replacing OPT's point $p$ with greedy's point $e$ therefore loses no coverage and can only gain coverage of later intervals whose start falls in $(p, e]$. Repeating this exchange, one point at a time, transforms any optimal solution into exactly greedy's point set without ever increasing its size — so greedy's count equals the optimum.

Why "Sort by End Time" Keeps Showing Up (and Where It Doesn't)

Interval Covering's exchange argument above has the same shape as Activity Selection's proof (Part 16, section 4): both sort by end time, and both show that committing as early as possible — the earliest-finishing activity, or a covering point pushed only as far as the current interval's own end — can never make later choices worse, only ever as good or better, because everything that follows sits at least as far to the right. When a family of greedy algorithms shares that shape, you do not need to rederive it from scratch each time; you need to identify which quantity plays the role of "the thing that, committed to as early as possible, only helps."

Minimum Meeting Rooms is a different animal. It does not select a subset of intervals or place covering points — it counts how many intervals are simultaneously alive at the worst moment, which is a question about overlap, not about end-time ordering (the heap approach in fact sorts by start time). Its correctness argument is a staying-ahead / exact-accounting argument rather than an exchange argument: the heap always holds exactly one end time per currently active meeting — never more, never fewer — so the heap's size at any instant is precisely the number of meetings alive at that instant. No algorithm can use fewer rooms than the maximum number of meetings ever alive simultaneously, since that many meetings are, by definition, pairwise overlapping and each needs its own room; the greedy heap process demonstrably reaches exactly that maximum and no higher. Matching a provable lower bound is its own correctness proof — different in shape from an exchange argument, but no less rigorous.

6. Complexity Comparison

All three approaches share the same $O(n \log n)$ time bound, dominated by sorting; they differ in what they hold in memory while sweeping.

7. Applications and Alternatives

Choose the min-heap when you also need to know which room each meeting is assigned to (the heap naturally tracks room identity alongside end time); choose the sweep line when you only need the count and want to avoid heap bookkeeping. Interval covering has no meaningful alternative structure beyond the sort-and-skip greedy — its simplicity is the point, and reaching for a heap or DP table here would be solving a harder problem than the one asked.

8. Exercises and Mastery

Easy

1. Run Minimum Meeting Rooms by hand (heap or sweep line, your choice) on [(0,30), (5,10), (15,20)]. State the room count and which meetings share a room.

Medium

1. Run Interval Covering by hand on [(1,2), (3,4), (2,3), (5,7), (6,8)]. Sort by end time first, then trace the placement decisions the way section 5's table does.

Hard

1. Suppose every meeting's start and end can each be shifted by up to a small tolerance $\delta$ before or after its stated time, and you may choose the shifts to minimize the number of rooms needed overall. Describe, at a design level, how you would decide whether shifting helps in a given schedule, what information the min-heap approach would need in addition to end times, and why this is no longer simply "run the same greedy with slightly different numbers."

Review rhythm: tomorrow, reconstruct both algorithms from memory, including which sort key each uses and why they differ; next week, implement both in a language not shown here; several weeks later, identify a new problem in the wild that reduces to "peak simultaneous overlap" versus one that reduces to "fewest covering points," and explain the distinction to someone who has only read Part 16.

9. Summary Cheat Sheet

• Interval-scheduling problems share raw material (intervals) but not one algorithm — each variant needs its own sort key and its own correctness argument.
• Activity Selection and Maximum Non-Overlapping Intervals (Part 16) sort by end time and are proven by an exchange argument; this lesson does not repeat them.
• Minimum Meeting Rooms sorts by start time and maintains a min-heap of room end times; the answer is the heap's peak size, which equals its final size because it never shrinks.
• The sweep-line alternative counts $+1$ at every start and $-1$ at every end (ties: end before start); the running maximum is the room count.
• Interval Covering sorts by end time and greedily places a point at the current uncovered interval's end, skipping everything that point already covers.
• Meeting Rooms is proven correct by a staying-ahead / exact-accounting argument (heap size = simultaneous overlap, a matched lower bound); Interval Covering is proven correct by an exchange argument, the same shape as Activity Selection's.
• All three run in $O(n \log n)$ time, dominated by sorting.