Interval Partitioning and Graph Colors

In interval partitioning, the goal is to schedule all given intervals using the minimum number of resources (like rooms). This is distinct from interval scheduling, which selects a maximum compatible subset for a single room. Because every interval must be scheduled, a greedy algorithm that assigns the first available room can attain the minimum possible number of rooms, matching the graph's maximum simultaneous overlap (its clique number).

Worked example: The Nested Case

Consider the Nested preset with three intervals: [0, 5], [1, 4], and [2, 3]. We want to find the minimum number of rooms needed using the "Half open" rule (where the end time is exclusive, but here all intervals strictly overlap).

Sort the intervals by their start times: [0, 5], [1, 4], [2, 3].
Assign [0, 5] to Room 0.
For [1, 4], the start time 1 is less than the end time 5 of Room 0, so it cannot be placed in Room 0. It must be assigned to Room 1.
For [2, 3], the start time 2 is less than the end times of Room 0 (5) and Room 1 (4), so it goes to Room 2.

At time t = 2.5, all three intervals are active simultaneously. This means the maximum overlap is 3. Consequently, the minimum number of rooms required is exactly 3. The greedy algorithm confirms this lower bound.

Experiment: Endpoint Rules

Let's explore how endpoint rules affect the maximum overlap and room assignments. Open the Interval Partitioning and Graph Colors module.

Select the Touching intervals preset, which consists of [0, 1], [1, 2], and [2, 3].
Ensure the Endpoint rule is set to Half open.
Observe that the Maximum overlap is 1, and the Minimum rooms is 1. Under the half-open rule, interval [0, 1) does not overlap with [1, 2) at t = 1, so they can share the same room.
Now change the Endpoint rule to Closed.
Observe that the Maximum overlap becomes 2, and the Minimum rooms jumps to 2. Under the closed rule, [0, 1] and [1, 2] overlap at exactly t = 1, forcing them into separate rooms.

Limitations

The greedy interval coloring algorithm assumes that all intervals are known in advance (offline) and can be sorted. It does not handle online scenarios where intervals arrive one by one and must be scheduled immediately. Additionally, this model assumes all rooms are identical and available at all times. If rooms have different capacities or restricted time windows, a more complex resource allocation or graph coloring algorithm would be required.

References

This interval partitioning approach is widely taught as an application of greedy algorithms.

Kleinberg and Tardos, Algorithm Design: Discusses the greedy algorithm for interval partitioning and proves that the number of rooms equals the depth (maximum overlap) of the intervals.

Interval Partitioning and Graph Colors