Interval Scheduling

The Problem

Notation	Meaning
$n$	Number of intervals
$s(i)$	Start time of $i$th interval. The convention that the interval has to start at time step $s(i)$
$f(i)$	Finish time of $i$th interval. The convention that the interval has to finish at time step $f(i)-1$
$[\ell,r)$	The interval $\{\ell,\dots,r-1\}$
$\mathcal{O}$	An optimal schedule

Greedy Algorithm for Interval Scheduling

Notation	Meaning
$S$	At any point of the run of the algorithm the set of intervals that have been chosen/scheduled.
$R$	At any point of the run of the algorithm the set of intervals that do not have conflict with intervals in $S$.
$S^*$	The final schedule output by the algorithm.

Scheduling to minimize maximum lateness

The Problem

Notation	Meaning
$n$	Number of jobs.
$d_i$	Deadline for $i$th job: job needs to finish by time $d_i-1$.
$t_i$	Duration for $i$th job: job takes $t_i$ time units.
$s(i)$	Scheduled start time for job $i$.
$f(i)$	Scheduled finish time for job $i$: $f(i)=s(i)+t_i$.
$\ell_i$	Latness of job $i$, $\ell_i=\max(0,f(i)-1-d_i)$.
$L(S)$	Maximum latness of scheule $S$. Defined as $L(S)=\max_{i\in S} \ell_i$.
$\text{idle}(S)$	Idle time of schedule $S$. Recall that the idle time of $S$ is $\max_{i < n} (s(i+1)-f(i))$.
$\#\text{inv}(S)$	Number of inversions in $S$. Recall that $(i,j)$ is an inversion in $S$ if $i$ is scheduled before $j$ but $d_i > d_j$.

Greedy Algorithm for Scheduling to Minimize Maximum Lateness

Notation	Meaning
$S$	Schedule output by Greedy algorithm. Schedule is set of pairs $(s(i),f(i))$.
$\mathcal{O}$	An optimal schedule.

Weighted Interval Scheduling

The Problem

Notation	Meaning
$n$	Number of intervals
$s_i$	Start time of $i$th interval. The convention that the interval has to start at time step $s_i$
$f_i$	Finish time of $i$th interval. The convention that the interval has to finish at time step $f_i-1$
$v_i$	Value of the $i$th interval. If $i$ is added to the schedule, we get a value of $v_i$.
$S$	$S\subseteq [n]$ is a schedule if no two intervals in $S$ conflict with each other.
$v(S)$	Value of schedule $S$. Defined as $\sum_{i\in S} v_i$.
$\mathcal{O}$	An optimal schedule

Dynamic Programming Algorithm for Wighted Interval Scheduling

Notation	Meaning
$\mathcal{O}_j$	An optimal solution for the first $j$ jobs.
$\text{OPT}(j)$	Value of any optimal solution for first $j$ jobs. I.e. $\text{OPT}(j)=v(\mathcal{O}_j)$.
$p(j)$	Largest index $i< j$ such that $i$ and $j$ do not conflict (under the assumption that $f_1\le f_2\le \cdots \le f_n$).