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

Interval scheduling chooses the largest number of compatible jobs on one timeline. Choosing the earliest start can keep one long job while excluding many short ones. Choosing shortest duration alone can also block a better arrangement. Earliest finish is the criterion that preserves the most remaining time.

Jobs occupy half-open intervals: a job starting exactly when another ends is compatible. The result also needs a canonical tie rule because several maximum-size schedules may exist.

Choosing the session that frees the room first

Sort candidates by end time, then start time, then ID. Accept a candidate when its start is at least the most recently accepted end. An exchange argument explains the greedy choice: replace the first job of an optimal schedule with the earliest-finishing candidate. The replacement ends no later, so it cannot invalidate that schedule's later jobs. Repeat on the remaining suffix.

An initial last-end value of zero wrongly rejects valid negative-time jobs. Use a separate no-job-yet state. Validate every duration before producing an answer. Sorting the caller's array in place would violate preservation, so sort a copy; do not mutate nested job records either.

Use the supplied compareText helper for the final ID tie-break. Default UTF-16 sorting and localeCompare do not guarantee Unicode code-point order. A comparator must compare numeric times first and consult ID only when those times tie.

import { compareText } from "./exercise.mjs";
const a = ["z", 0, 2], b = ["a", 0, 2];
const order = a[2] - b[2] || a[1] - b[1] || compareText(a[0], b[0]);
console.log(order > 0); // true: equal times put a before z
console.log(2 >= 2); // true: touching intervals are compatible

Where the greedy proof stops

A subset-enumerating prototype is exponential and must still reproduce the canonical optimum. Final sorting costs O(n log n), followed by O(n) selection; a copied array uses O(n) space. This solves maximum-count unweighted scheduling, not maximum total profit. Weighted jobs require a different recurrence, and multiple simultaneous resources need a different feasibility model.

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