### PROBLEM LINK:

**Author:** Khadar Basha

**Tester:** Anton Lunyov

**Editorialist:** Anton Lunyov

### DIFFICULTY:

Simple

### PREREQUISITES:

Dynamic Programming, Interval Scheduling

### PROBLEM:

You are given a set of orders for conducting events. Each event has its starting hour, ending hour and a compensation for its conducting. The task is to find the set of orders with maximal possible compensation such that corresponding events do not overlap.

### QUICK EXPLANATION:

Denote event with starting hour **S** and ending hour **E** as **(S, E)**−event. Since range of hours is small we can create a two-dimensional array **C[0…48][0…48]** with meaning **C[S][E]** is the maximal compensation among all **(S, E)**−events. For convenience we put **C[S][E] = 0** if there are no **(S, E)**−events. Then the problem can be solved by dynamic programming. Denote by **maxC[E]** the maximal possible compensation if we consider only events with ending hour **≤ E**. Then

maxC[0] = 0; maxC[E] = max{maxC[S] + C[S][E] : 0 ≤ S < E}, for 1 ≤ E ≤ 48;

and the answer is **maxC[48]**.

### EXPLANATION:

The array **C[0…48][0…48]** should be filled initially with zeros:

for S from 0 to 48 for E from 0 to 48 C[S][E] = 0

**Tip.** *In C/C++/Java you should create this array as:* `int C[49][49];`

After that it can be filled with correct numbers just in the stage of reading information about orders. Namely, if order with parameters **Si**, **Ei** and **Ci** was read then you should replace **C[S][E]** by **Ci** if **Ci** is greater than the old value of **C[S][E]**:

read Si, Ei, Ci C[Si][Ei] = max(C[Si][Ei], Ci)

The convention **C[S][E] = 0** if we have no **(S, E)**−events can be treated as adding of dummy events with zero compensation for each such pair **(S, E)**. Clearly adding of such events does not change the answer since their compensations are zeros. So now we have **(S, E)**−events (possibly dummy) for every pair **(S, E)** such that **0 ≤ S < E ≤ 48**.

Now we explain the formula for **maxC[E]**. The part **maxC[0] = 0** is obvious since we don’t have events with ending hour **≤ 0** and hence can’t get positive compensation. Now let **1 ≤ E ≤ 48**. Recall that **maxC[E]** is the answer for the problem if we consider only events with ending hour **≤ E**.

If we don’t have events with ending hour equals to **E** then the maximal possible compensation is not greater than **maxC[E − 1]** since all the remaining events lie on the segment **[0, E − 1]** and **maxC[E − 1]** is exactly the maximal possible compensation if all events has ending hour **≤ E − 1**. Clearly, **maxC[E − 1] ≤ maxC[E − 1] + C[E − 1][E]**.

Now assume that in optimal choice we have **(S, E)**−event with compensation **C[S][E]**. Since events should not overlap, all the remaining events lie on the segment **[0, S]**, so the maximal possible compensation for them is **maxC[S]** by definition of this number. Hence, the total compensation in this case is **maxC[S] + C[S][E]**. Clearly, in order to get **maxC[E]**, we should get the maximum of **maxC[S] + C[S][E]** over all **S < E**. So we arrive at the required formula for **maxC[S][E]**.

The pseudo-code for this part of solution can be written as follows:

for E from 0 to 48 maxC[E] = 0 for S from 0 to E − 1 maxC[E] = max(maxC[E], maxC[S] + C[S][E]) print maxC[48]

Thus, we get a solution with time complexity **O(N + H * H)** that requires **O(H * H)** memory, where **H = 48** is the hour range. Here summand **N** corresponds to input stage while summand **H * H** corresponds to all other stages (initializing **C[0…48][0…48]**, calculating DP). You can see an implementation of this approach in first tester’s solution.

### ALTERNATIVE SOLUTION:

Now we discuss the solution that doesn’t make any assumptions on hour range. For this let’s save all events in some array and sort them in ascending order of ending hour. We number events from **1** to **N** and denote by **S[i]**, **E[i]** and **C[i]** the corresponding parameters of the **i**-th event. Similarly to the previous solution denote by **maxC[i]** the maximal possible compensation we can get by using first **i** events **of this sorted array**. Denote also by **ind[i]** the largest index **j** such that **j**-th event does not overlap with **i**-th event. If all events with smaller indexes overlap with the **i**-th one we set **ind[i] = 0**. Then it is clear that

maxC[0] = 0; maxC[i] = max(maxC[i − 1], maxC[ind[i]] + C[i]), for i from 1 to N;

and the answer is **maxC[N]**.

Here first argument of maximum means that we do not take the **i**-th event, while the second argument means that we take it, and since the remaining events should not overlap with it we move to **maxC[ind[i]]**.

The index **ind[i]** can be found by binary search. Indeed, **ind[i]** is the largest index **j** such that **E[j] ≤ S[i]**. So the following pseudo-code will find **ind[i]** in **O(log N)** time:

L = 0 R = i while L + 1 < R do M = L + (R − L) / 2 if E[M] ≤ S[i] then L = M else R = M ind[i] = L

Thus we get a solution with time complexity **O(N * log N)** that requires **O(N)** memory, if we use some fast sorting algorithm like Quicksort or Merge sort. The complexity of each step is:

- Input:
**O(N)**. - Sorting:
**O(N * log N)**. - Calculating
**ind[i]**for each**i**:**O(N * log N)**. - Calculating DP:
**O(N)**.

Also note that we don’t need actual array**ind[1…N]**since we can calculate it during calculation of DP, that is, we can unite 3-rd and 4-th steps together. See the second tester’s solution as a reference.

But in this problem you can find **ind[i]** in a simple **O(N)** loop since **N** is small enough, as well as use some simple **O(N * N)** sorting algorithm. See the setter’s solution as a reference.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s first solution can be found here.

Tester’s second solution can be found here.