Skip to content

Interval Scheduling

Problem

Given a collection of intervals, find the maximum number of non-overlapping intervals (activity selection problem).

Approach

Sort intervals by end time. Greedily select the next interval whose start time is >= the end time of the last selected interval. This maximizes the number of non-overlapping intervals.

When to Use

Activity selection / resource booking — "max non-overlapping intervals", "minimum removals for no overlap", "room scheduling". Sort by end time, greedily pick earliest-finishing. Aviation: gate/runway slot allocation.

Complexity
Time O(n log n)
Space O(1) (excluding input sort)

Implementation

interval_scheduling

Interval Scheduling — maximum non-overlapping intervals.

Problem

Given a collection of intervals, find the maximum number of non-overlapping intervals (activity selection problem).

Approach

Sort intervals by end time. Greedily select the next interval whose start time is >= the end time of the last selected interval. This maximizes the number of non-overlapping intervals.

When to use

Activity selection / resource booking — "max non-overlapping intervals", "minimum removals for no overlap", "room scheduling". Sort by end time, greedily pick earliest-finishing. Aviation: gate/runway slot allocation.

Complexity

Time: O(n log n) Space: O(1) (excluding input sort)

max_non_overlapping 

max_non_overlapping(
    intervals: Sequence[Sequence[int]],
) -> int

Return the maximum number of non-overlapping intervals.

max_non_overlapping([[1, 3], [2, 4], [3, 5], [0, 6]]) 2

Source code in src/algo/greedy/interval_scheduling.py 
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def max_non_overlapping(intervals: Sequence[Sequence[int]]) -> int:
    """Return the maximum number of non-overlapping intervals.

    >>> max_non_overlapping([[1, 3], [2, 4], [3, 5], [0, 6]])
    2
    """
    if not intervals:
        return 0

    sorted_iv = sorted(intervals, key=lambda iv: iv[1])
    count = 1
    end = sorted_iv[0][1]

    for start, finish in sorted_iv[1:]:
        if start >= end:
            count += 1
            end = finish

    return count

min_removals 

min_removals(intervals: Sequence[Sequence[int]]) -> int

Return the minimum number of intervals to remove for no overlap.

Equivalent to len(intervals) - max_non_overlapping(intervals).

min_removals([[1, 2], [2, 3], [3, 4], [1, 3]]) 1

Source code in src/algo/greedy/interval_scheduling.py 
46
47
48
49
50
51
52
53
54
def min_removals(intervals: Sequence[Sequence[int]]) -> int:
    """Return the minimum number of intervals to remove for no overlap.

    Equivalent to len(intervals) - max_non_overlapping(intervals).

    >>> min_removals([[1, 2], [2, 3], [3, 4], [1, 3]])
    1
    """
    return len(intervals) - max_non_overlapping(intervals)
tests/greedy/test_interval_scheduling.py
"""Tests for interval scheduling."""

from algo.greedy.interval_scheduling import max_non_overlapping, min_removals


class TestMaxNonOverlapping:
    def test_basic(self) -> None:
        assert max_non_overlapping([[1, 3], [2, 4], [3, 5], [0, 6]]) == 2

    def test_no_overlap(self) -> None:
        assert max_non_overlapping([[1, 2], [3, 4], [5, 6]]) == 3

    def test_all_overlap(self) -> None:
        assert max_non_overlapping([[1, 10], [2, 5], [3, 8]]) == 1

    def test_single_interval(self) -> None:
        assert max_non_overlapping([[0, 1]]) == 1

    def test_empty(self) -> None:
        assert max_non_overlapping([]) == 0

    def test_touching_intervals(self) -> None:
        assert max_non_overlapping([[1, 2], [2, 3], [3, 4]]) == 3


class TestMinRemovals:
    def test_basic(self) -> None:
        assert min_removals([[1, 2], [2, 3], [3, 4], [1, 3]]) == 1

    def test_no_removals_needed(self) -> None:
        assert min_removals([[1, 2], [3, 4]]) == 0

    def test_all_same(self) -> None:
        assert min_removals([[1, 2], [1, 2], [1, 2]]) == 2

Implement it yourself

Run: just challenge greedy interval_scheduling

Then implement the functions to make all tests pass. Use just study greedy for watch mode.

Reveal Solution

interval_scheduling

Interval Scheduling — maximum non-overlapping intervals.

Problem

Given a collection of intervals, find the maximum number of non-overlapping intervals (activity selection problem).

Approach

Sort intervals by end time. Greedily select the next interval whose start time is >= the end time of the last selected interval. This maximizes the number of non-overlapping intervals.

When to use

Activity selection / resource booking — "max non-overlapping intervals", "minimum removals for no overlap", "room scheduling". Sort by end time, greedily pick earliest-finishing. Aviation: gate/runway slot allocation.

Complexity

Time: O(n log n) Space: O(1) (excluding input sort)

max_non_overlapping 

max_non_overlapping(
    intervals: Sequence[Sequence[int]],
) -> int

Return the maximum number of non-overlapping intervals.

max_non_overlapping([[1, 3], [2, 4], [3, 5], [0, 6]]) 2

Source code in src/algo/greedy/interval_scheduling.py 
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def max_non_overlapping(intervals: Sequence[Sequence[int]]) -> int:
    """Return the maximum number of non-overlapping intervals.

    >>> max_non_overlapping([[1, 3], [2, 4], [3, 5], [0, 6]])
    2
    """
    if not intervals:
        return 0

    sorted_iv = sorted(intervals, key=lambda iv: iv[1])
    count = 1
    end = sorted_iv[0][1]

    for start, finish in sorted_iv[1:]:
        if start >= end:
            count += 1
            end = finish

    return count

min_removals 

min_removals(intervals: Sequence[Sequence[int]]) -> int

Return the minimum number of intervals to remove for no overlap.

Equivalent to len(intervals) - max_non_overlapping(intervals).

min_removals([[1, 2], [2, 3], [3, 4], [1, 3]]) 1

Source code in src/algo/greedy/interval_scheduling.py 
46
47
48
49
50
51
52
53
54
def min_removals(intervals: Sequence[Sequence[int]]) -> int:
    """Return the minimum number of intervals to remove for no overlap.

    Equivalent to len(intervals) - max_non_overlapping(intervals).

    >>> min_removals([[1, 2], [2, 3], [3, 4], [1, 3]])
    1
    """
    return len(intervals) - max_non_overlapping(intervals)