= Weighted interval scheduling
{title2=$\max\sum_{i\in S}w_i$}
<Weighted interval scheduling> assigns each job a reward $w_i$ and maximizes their sum over compatible jobs. Earliest finish can fail for this different <objective function>; <dynamic programming> can compare alternatives.<6.046J Design and Analysis of Algorithms, Spring 2015/Lecture 1: Introduction>[6.046J Design and Analysis of Algorithms, Spring 2015; Printed pp. 4–5, Weighted Interval Scheduling and Dynamic Programming]{ref}
For a separate two-job example, let $X=[0,2)$ have reward one and $Y=[1,3)$ reward ten. Earliest finish accepts $X$ and rejects $Y$, earning one; the optimum accepts $Y$, earning ten. Replacing $Y$ by $X$ preserves job count but loses reward. Thus the <interval scheduling> <exchange argument> proves the unit-value theorem only: its preserved quantity must match the intended <objective function>.
Back to article page
