Greedy interval scheduling

A recording room has more requested sessions than it can host. Every accepted session counts equally, and bookings may touch at their endpoints. The goal is to accept as many as possible.

Taking the first request is easy to justify administratively, but not algorithmically: one long early booking may exclude several short ones. The useful greedy choice is the compatible session that finishes first.

Fitting more sessions into one room

Select compatible half-open intervals with a deterministic earliest-finish optimum. Selection order must account for end time, start time, and identifier ties.

Choosing earliest start or shortest duration can block a larger compatible collection. Exploring all subsets can establish correctness for small inputs, but the exchange argument behind earliest finish avoids that exponential search.

Choosing the session that frees the room first

A booking [0, 8) conflicts with [1, 3), [3, 5), and [5, 7). Earliest start accepts one session; earliest finish accepts three. To justify the latter, take an optimal schedule and replace its first booking with the earliest-finishing one. It ends no later, so the rest of that schedule still fits. Repeat the argument on what remains.

An earliest-ending compatible interval leaves at least as much room for later choices as any competing first interval. Sorting by end/start/id makes the optimum canonical. Touching half-open intervals are compatible. Prototype may enumerate subsets; final sorting plus greedy scan costs O(n log n) time and O(n) copied storage.

Touching half-open intervals are compatible; the overlap predicate makes the boundary explicit:

import java.util.*;

class Example {
    public static void main(String[] args) {
        long firstStart = 0, firstEnd = 2;
        long secondStart = 2, secondEnd = 4;
        boolean overlap = firstStart < secondEnd && secondStart < firstEnd;
        assert !overlap;
        assert secondStart >= firstEnd;
    }
}

Replacing a strict comparison with <= would reject adjacent intervals incorrectly. The final canonical sort must also break equal-end ties by start and ID, so independent implementations agree on the selected sequence.

Where the greedy proof stops

Interval scheduling is useful for maximizing count under exclusive-resource time constraints. It solves that specific objective; adding weights, multiple rooms, or setup costs can invalidate the same greedy rule.

Require unique job IDs and end > start, otherwise IllegalArgumentException. Return IDs selected after sorting by (end,start,id) and accepting each start >= the preceding selected end. Empty input returns empty. Example (b,0,2),(a,0,2),(c,2,3) selects a,c.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

If the room starts charging different fees per session, revisit the objective before reusing the greedy rule.