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 time leaves the largest remaining suffix of time available. Exchange the first job of any optimal schedule for a job ending no later: the replacement cannot invalidate its later jobs. Repeating this exchange supports greedy selection.

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.

// Compare (end,start,id), rather than the input tuple's (id,start,end).
auto key=[](const auto& j){return std::tuple{std::get<2>(j),std::get<1>(j),std::get<0>(j)};};

Where the greedy proof stops

The canonical tie rule matters even when many different schedules have equal size. Touching half-open intervals are compatible: start equal to the previous end is accepted. A numeric initial end of zero would accidentally reject valid negative-time jobs; use an optional previous end. Validate every duration and ID uniqueness before producing a result. Sorting a copied vector protects caller order and costs O(n log n). The acceptance scan uses constant state excluding output.

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.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

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