Weighted Interval Scheduling

Folklore (CLRS style), 1955

Operational researchers and economists sketched greedy-style scheduling from the mid-century onward without a single attributable author—Algorithm textbooks crystallize its bottom-up recurrence with preprocessing. Indices sort by earliest finish-times, predecessors mark the farthest disjoint interval west of each candidate, and each decision compares skipping versus chaining the weighted reward with that predecessor optimum. Slate geometry, gold outlines, teal winners, coral totals stay within the mute palette cues while aligning with pedagogical exposition in modern texts.