Answer to Question #239114 in Algorithms for Zahid

Question

Suppose you are a manager of an event management company. Your team is responsible for running various events. Each event, depending on its nature, runs for varied lengths. Your company policy is such that you charge a flat amount for each event your team is managing (irrespective of the duration a particular event). The size of the team that you are running is such that your team can manage to run one event at a particular time i.e. your company is unable to run multiple events at a particular time. More formally, if there are two events i and j, the events are mutually compatible (i.e. you can select both i andj) if s>f, ors,>fwhere s; and fi are the start and finish time of the event i. You are required to select events that your team is going to manage so that you can maximize the profit for your company. The following table shows some candidate events for your company to manage for a particular day. Find out which events would you select such that you can maximize the profit for your company.

Answer 1

Let {t_k}_k=1,..,n set of all right ends of events in increasing order. For each time t_k let we leave only one shortest event with this end.

Next we use dynamic programming method Let F_k be maximal number of mutually disjoint possible events with right ends less or equal to t_k and t_1k be left end of event with right end t_k , q_k=1 iff event (t_1k,t_k) should be used in optimal solution on subinterval [0,t_k], also let k(t)=max{k: t_k<t. or 0 if such tk does not exist. Then next formulas can be used

F₀=0, F₁=1,q₁=1. F_k=max{F_k-1,1+ $F_{k(t_{1k})}$ ),k=2,..,n and if F_k>F_k-1 q_k=1 otherwise q_k=0

Then values F_n,q_n will present solutiom on on the entire interval [0,24]

Let for example set {(1,10),(5,17),(12,23)} is given. We have n=3 and t₁=10,t₂=17,t₃=23. According to dynamic programming algorith we have:

F₀=0, F₁=1,q₁=1. Next. F₂=max{F₁,F_k(5)+1)=max{1,F₀+1)=max{1,1}=1.

F₃=max{F₂,F_k(12)+1)=max(1,F₁+1)=max(1,2)=2>F₂=> q₃=1. Going back we find that q₂=0,q₁=1. Thus for chosen example problem is solved with q1=1,q2=0,q3=1 and should manage events (1,10) and (12,23) it is maximal set of mutually disjoint events.