| Hide text Hide pseudo-code | |
|
The task is to schedule n events in such a way that there is no overlapping events and
the combined profit is maximum. Use the following algorithm.
The input contains the events and the corresponding profits. The output is the optimal combined profit in Result[0] (for the selected events in Select table).
|
1 SelectEvents(Begin, End, Profit, n) {
2 Result[n-1] = Profit[n-1];
3 Select[n-1] = TRUE;
4 for (int i=n-2; i>=0; i--) {
5 j = earliest event such that Begin[j] >= End[i] or j = n;
6 if (Profit[i] + Result[j] >= Result[i+1]) {
7 Select[i] = TRUE;
8 Result[i] = Profit[i] + Result[j];
9 } else {
10 Select[i] = FALSE;
11 Result[i] = Result[i+1];
12 }
13 }
14 clear overlapping true values from select table, i.e., starting from
15 beginning (i=0), if there exists such an event i+k, k>0 that overlaps
16 with event i then event i+k is set false in select table.
17 }
|