## Dynamic programming

 Hide textShow text Hide pseudo-codeShow 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 (for the selected events in Select table). Input: tables Begin[0..n-1], End[0..n-1] (start and end times of events), Profit[0..n-1] (the earnings if this event was selected), and the number of events n Output: tables Select[0..n-1] (true or false depending on whether this event was selected or not, respectively), and Result[0..n] (for each index i, this denotes the cumulative profit for events i..n; note that the result table is larger than the rest of the tables on purpose) ``` 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 } ```