I came across this question in my textbook and it is stumping me. Namely, what is stumping me is the final two cases when creating the recurrance relation. I sort of understand that you have to take the maximum of the two cases, but what I can't quite figure out is how this works when there is 2 lectures. Lets say the first lecture in the list of ordered lectures is $L$$1$,furthermore, lets assume that zero people attend this lecture, and the end time of this lecture is after the start time of the second lecture ($L$$2$), and also that 100 people attend $L$$2$. This means that it is impossible to schedule both lecture $L$$1$ and$L$$2$ in any schedule. The algorithm says for considering only lecture 1, it is either in the optimal solution or it is not. In this case $L$$1$ is not in the optimal schedule, so we go down the path of $(case$ $ii)$, which says that $T(L$$1$$)$ $=$ $T(L$$1$$-1)$ = $T(L$$0$$)$, but $L$$0$ does not exist. So it cannot apply this step of the algorithm, and therefore must either choose $case$ $i$ which would imply $L$$1$ is part of the optimal schedule, or the algorithm would break.
I have a feeling my thinking is wrong somewhere, but I cannot seem to reason with this question.
QUESTION FROM BOOK
The goal is to schedule as many talks as possible in a single lecture hall. These talks have preset start and end times; once a talk starts, it continues until it ends; no two talks can proceed at the same time; and a talk can begin at the same time another one ends. Suppose that our goal is not to schedule the most talks possible, but rather to have the largest possible combined attendance of the scheduled talks.
We formalize this problem by supposing that we have $n$ talks, where talk $j$ begins at time $s$$j$ , ends at time $e$$j$ , and will be attended by $w$$j$ students. We want a schedule that maximizes the total number of student attendees. That is, we wish to schedule a subset of talks to maximize the sum of $w$$j$ over all scheduled talks. (Note that when a student attends more than one talk, this student is counted according to the number of talks attended.) We denote by $T(j)$ the maximum number of total attendees for an optimal schedule from the first $j$ talks, so $T(n)$ is the maximal number of total attendees for an optimal schedule for all $n$ talks. We first sort the talks in order of increasing end time. After doing this, we renumber the talks so that $e$$1$ $≤$ $e$$2$ $≤ ⋯ ≤ e$$n$. We say that two talks are compatible if they can be part of the same schedule, that is, if the times they are scheduled do not overlap (other than the possibility one ends and the other starts at the same time). We define $p(j)$ to be largest integer $i, i < j$, which $e$$i$ $≤ s$$j$, if such an integer exists, and $p(j) = 0$ otherwise. That is, talk $p(j)$ is the talk ending latest among talks compatible with talk $j$ that end before talk $j$ ends, if such a talk exists, and $p(j) = 0$ if there are no such talks.
To develop a dynamic programming algorithm for this problem, we first develop a key recurrence relation. To do this, first note that if $j ≤ n$, there are two possibilities for an optimal schedule of the first $j$ talks (recall that we are assuming that the $n$ talks are ordered by increasing end time): $(i)$ talk $j$ belongs to the optimal schedule or $(ii)$ it does not.
$Case (i):$ We know that talks $p( j) + 1, … , j − 1$ do not belong to this schedule, for none of these other talks are compatible with talk $j$. Furthermore, the other talks in this optimal schedule must comprise an optimal schedule for talks $1, 2, … , p(j)$. For if there were a better schedule for talks $1,2,…,p (j)$, by adding talk $j$, we will have a schedule better than the overall optimal schedule. Consequently, in case $(i)$, we have $T(j) = w$$j$$ + T(p(j))$.
$Case (ii):$ When talk j does not belong to an optimal schedule, it follows that an optimal schedule from talks $1, 2, … , j$ is the same as an optimal schedule from talks $1, 2, … , j − 1$. Consequently, in $case (ii)$, we have $T(j) = T(j − 1)$. Combining cases $(i)$ and $(ii)$ leads us to the recurrence relation
$T(j) = max(wj + T(p( j)), T( j − 1))$