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

Earliest finish leaves the largest remaining time horizon. An exchange argument replaces the first job of an optimal schedule with the no-later finishing greedy choice without reducing the number of later jobs. Earliest start and shortest duration do not provide the same guarantee.

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.

a := Job{ID: "first", Start: 0, End: 2}
b := Job{ID: "next", Start: 2, End: 3}
fmt.Println(b.Start >= a.End) // touching is compatible

Where the greedy proof stops

Tie ordering creates a reproducible optimum even when several schedules have equal cardinality. Validate the complete inventory before selecting anything; duplicate identities make output ambiguous. This models one exclusive resource with equal-value jobs. Weighted jobs or multiple resources require different optimization.

A sorted copy and one compatibility scan take O(n log n) time and O(n) copy space. The reference search has exponentially many subsets. Equal rewards are essential: weighted bookings, setup times, and multiple rooms require different reasoning, not just another sort key.

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