PROBLEM LINK:
Author: Vishal Khopkar
DIFFICULTY:
EASY
PREREQUISITES:
Dynamic programming, trees
PROBLEM:
We need to adjust some of the given events to be held at the stadium such that the stadium is used to its fullest.
QUICK EXPLANATION:
Well, there may be many solutions, the one I chose was using trees and dynamic programming.
EXPLANATION:
We first look at the Gantt chart shown on the problem page. There will be some events that can be chosen independently of others, i.e. if the event does not overlap with another, the two can be said to be independent. Now, I constructed the tree shown below and calculated the path consuming the largest time.
The approach used in 0-1 knapsack can be used here.
![Tree for event scheduling][1]
Solution
[1]: https://vishalkhopkar.files.wordpress.com/2016/11/rio2_expn.png
