Weighted Interval Scheduling

Input $n$ intervals $(s_i, f_i)$ with weight $v_i$

Output A compatible subset of intervals which maximises total weight

Suppose requests are sorted by ascending finish time, that is $f_1\leq f_2 \leq ... \leq f_n$. Let $p(j)$ be the largest index $i < j$ such that $i$ and $j$ are compatible and $p(j) = 0$ if there are no compatible intervals.

Consider the final interval, $n$. If this interval is included in an optimal solution then any intervals between $p(n)$ and $n$ are incompatible by definition of $p(n)$. The optimal solution therefore contains $n$ and some intervals from $\lbrace 1,...,p(n)\rbrace$.

If $n$ is not in the optimal solution then the optimal solution only contains intervals $\lbrace 1,...,n-1 \rbrace$. To maximise the total weight of the schedule, the maximum of these two options is taken, which results in a recursive definition as follows: $$ M[j] = \begin{cases} 0 & j=0\\ \max\left(M[j-1], M[p(j)]+v_j \right) & \text{if } j > 0 \end{cases} $$

This finds the maximum weight of a schedule up to an interval $j$. It considers the maximum of $M[j-1]$, which is the case where $j$ is not in the optimal solution and $M[p(j)] + v_j$, which is the case where the $j$ is in the optimal solution. By including the maximum weight at each stage, the final schedule weight is guaranteed to be maximum.

Complexity

Implementing the above recursively takes at worst exponential time. This can be improved to linear by using memoisation.

for i from 1 to n in intervals sorted by finish time:
    calculate M[i]

This takes $O(n)$ time, assuming the intervals are already sorted and $p(j)$ has been calculated for each interval. This is because addition, subtraction, $\max$ and lookup for $M$, $p$ and $v$ is $O(1)$, so over $n$ intervals the total time taken is $O(n)$.

Finding a solution

The above algorithm calculates the maximum value of a schedule, but does not give the schedule itself. The values calculated can be used to find the schedule.

$$ S[j] = \begin{cases} {j} \cup S[p(j)] & \text{if }M[j] > M[j-1]\\ S[j-1] & \text{otherwise} \end{cases} $$

Then

for i from 1 to n in intervals:
    calculate S[i]

The complexity of this algorithm is $O(n)$. The schedule of maximum weight is then given by $S[n]$.