Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Greedily Schedule Events based on value/hours

, ,
Problem Detail:

Suppose we are given a list of $n$ events $E = \{E_1, E_2, \ldots, E_n\}$ where each $E_i$ is represented by $(s_i, h_i, v_i)$ or $(start, hours, value)$. So if you attend an entire event that lasts 5hrs and has a value of 10 then you will gain 10 points. If you only attend for 3 hours, you only get 3*(10/5) = 6 points. The output that the algorithm should produce is the maximum number of points that can be obtained by attending combinations of various events. Note: you are allowed to leave and come back to an event.

My Algorithm (pseudocode):

• Sort all the events $E$ by order of their $v_i/h_i$ ratio to produce a new set of events $E'$ such that $E'[1]$ has a higher value/hours ratio than $E'[2]$, $E'[3]$, etc...
• $max = 0$
• For each event $e \in E'$
• $h =$ hours that have not yet been taken
• $max\ += h* (e_{v_i}/e_{h_i})$

Note: I did not specify in the algorithm how to determine the hours that have been scheduled/taken already but you can assume that there is an array that flags hours that have been scheduled.

I do believe that my algorithm gives the optimal result, but how do I prove this?

I'm assuming that the value given to $h$ in each step is "number of hours during the running of the event, which are not yet covered". (Your wording is somewhat ambiguous.)

In the following I'll assume that all events start and end at full hours. For real valued times, just replace hours by an amount of time small enough that all the differences between relevant moments (start and end times) are multiples of that amount.

From the constraints given, we see that the event visited at one point in time has no influence on the profit we can make at a different moment in time. Thus, the optimal solution will be to visit the most profitable event at each point in time, i.e. during each hour. Now, we only have to show that the algorithm achieves this:

Assume that there is an hour $h$ during which the algorithm suggests to visit event $e$, while visiting $e'$ would be more profitable. Since $e'$ is more profitable, it will have been put before $e$ during the first step of the algorithm. Furthermore, since $e'$ has been scheduled for $h$, $h$ must have been available when the algorithm processed $e$ and (since the algorithm never frees an hour) also when it processed $e'$. But this means that the algorithm would have scheduled $e'$ for hour $h$, contradicting our assumption. Thus we conclude that the algorithm is correct.