I'm reviewing algorithms, and I've come across this problem. At first, it seemed like an interval scheduling problem to me, but now I think it is a dynamic programming problem. I'm not sure how to solve this. I'd appreciate if someone could show me a solution.
Suppose you are an employee. Your boss has sent you to attend a conference. The conference lasts $n$ minutes. In the course of this conference, there are $m$ talks you can attend. Your boss has ordered that you must attend talks for the entirety of the conference, i.e. all $n$ minutes.
The talks have two quantified properties: a tuple (start-minute, end-minute) and stressfulness, a variable fixed cost incurred whenever you enter a talk. You seek to minimize the total stressfulness of the conference. Moreover, you are free to leave or enter a talk whenever you please. Find an efficient algorithm to pick the talks to attend.
The last part is critically important: it means that you can choose overlapping intervals to satisfy the problem.
In case it is not fully clear, here is an example for what the input data might look like. Let $L$ be the conference length, and $T$ the time-interval of each talk, and $S$ the stressfulness of each talk.
$L = 600$
Talk 1: $T=(0,400), S=15$
Talk 2: $T=(0,50), S=2$
Talk 3: $T=(50,300),S=8$
Talk 4: $T=(250,450),S=10$
Talk 5: $T=(400,500),S=4$
Talk 6: $T=(450,600),S=5$
You can choose Talk 1, Talk 5, and Talk 6 totalling $S=24$. The next-best alternative would be Talk 2, Talk 3, Talk 4, and Talk 6 at a total cost of $S=25$. Consequently, you choose to attend Talk 1, Talk 5, and Talk 6.
Best Answer
Here's a fun algorithm to solve this. The idea is that the employee's schedule is actually a sequence of talks, such that every adjacent talk in this sequence overlaps or touch each other. Thus, we can model this as a graph, where adjacent or touching talks have edge between them.
More formally, let's say we have $N$ talks, numbered $1$ through $N$. Let $S_i$ be the stressfulness of talk $i$. Create a graph with $N+2$ nodes: $N_i$, which corresponds to talk $i$, $N_s$, and $N_e$ (start and end node, respectively). Now, what we would like is to model the problem as a shortest path problem from $N_s$ to $N_e$, in such way that a path corresponds to a sequence of talks. For each pair of talks $N_i$ and $N_j$ that overlaps or touch each other, we create two directed edges, one from $N_i$ to $N_j$, with weight $S_j$, and another from $N_j$ to $N_i$ with weight $S_i$. Thus, we can imagine paying the "stress" when we enter the talk.
In addition, we create edge from $N_s$ to those talks that begin at time $0$, and from the talks that ends at time $L$ to $N_e$. The shortest path in this graph from $N_s$ to $N_e$ then gives the sequence of talks the poor employee must attend.
(Note that this does not work if any of the "stress" of the talks is negative)