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).

Experiment: Endpoint Rules

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

1. Select the Touching intervals preset, which consists of [0, 1], [1, 2], and [2, 3].
2. Ensure the Endpoint rule is set to Half open.
3. 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.
4. Now change the Endpoint rule to Closed.
5. 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.