Interval Partitioning

Partition intervals into the minimum number of groups such that no two intervals in the same group overlap.

This is equivalent to Meeting Rooms II: minimum groups = maximum overlap at any point.

function minGroups(intervals)
    events := []
    for interval in intervals
        events.add((interval.low, +1))
        events.add((interval.high, -1))

    sort events by position (ties: +1 before -1)

    maxOverlap := 0
    current := 0
    for (pos, delta) in events
        current := current + delta
        maxOverlap := max(maxOverlap, current)

    return maxOverlap

The tie-breaking rule depends on whether intervals are open or closed at endpoints. For closed intervals, process starts before ends at the same point.