Telescope Scheduling Predecessors

In Algorithm Design and Applications by Michael T. Goodrich and Roberto Tamassia Chapter 12.3 there is a presentation of a problem called the Telescope Scheduling problem.

Given n requests each with benefit, start time and end time, find the best combination of non conflicting requests that maximises the total benefit.

I understand the dynamic programming solution but for it the predecessor of each request is needed. That is "the largest index, j < i, such that requests i and j don’t conflict. If there is no such index, then define the predecessor of i to be 0." (I suppose i and j refer to the index of the request when sorted by end time)

It states that one can sort the requests by start time in one list L' and by end time in another list L and then "the predecessor of request i is literally the index of the predecessor in L of the value, si, in L'."

I cant see what that means.

Did you missed the following step?

Given a listing of $L$ ordered by finish times and another listing, $L'$, ordered by start times, then a merging of these two lists, as in the merge-sort algorithm (Section 8.1), gives us what we want.

Let us use the example in Figure 12.6: The telescope scheduling problem.

Listing $L$ is represented as $f_1,f_2,f_3,f_4,f_5,f_6,f_7$.

Listing $L'$ is represented as $s_1,s_2,s_4,s_3,s_7,s_5,s_6$.

A merging of these two lists gives us the following diagram.

$$\begin{aligned}
L&:\quad
f_0, \quad\phantom{\overbrace{s_1, s_2, s_4}^{\text inserted}} f_1, \phantom{\overbrace{s_3,}^{\text inserted}} f_2, \phantom{\overbrace{s_7,}^{\text inserted}} f_3,
\phantom{\overbrace{s_5,}^{\text inserted}} f_4, f_5, \phantom{\overbrace{s_6,}^{\text inserted}} f_6,f_7\\
L'&:\quad
\phantom{f_0,}\quad\overbrace{s_1, s_2, s_4}^{\text inserted} \phantom{f_1,}
\overbrace{s_3,}^{\text inserted} \phantom{f_2,}
\overbrace{s_7,}^{\text inserted} \phantom{f_3,}
\overbrace{s_5,}^{\text inserted} \phantom{f_4, f_5,}
\overbrace{s_6,}^{\text inserted} \phantom{f_6,f_7}\\
\end{aligned}$$
where $f_0$ is a virtual request with index $0$ that happens before all real requests.

The meaning of "the predecessor of request $i$ is literally the index of $\ $ the predecessor in $L$ $\ $of $\ $the value, $s_i$, in $L'$" should be clear now. For example,

• since the predecessor in $L$ of $s_1$ is $f_{\boldsymbol{0}}$, the predecessor of request $1$ is $0$.

• since the predecessor in $L$ of $s_2$ is $f_{\boldsymbol{0}}$, the predecessor of request $2$ is $0$.

• since the predecessor in $L$ of $s_7$ is $f_{\boldsymbol{2}}$, the predecessor of request $7$ is $2$.

StackExchange Computer Science Q#160605, answer score: 4