**Problem:**Given a conference room and a number of presentations with start and end time ( e.g., [4, 9], [5, 10]), try to make an arrangement which allows the conference room to be used for maximum time. Overlapping presentations can't be in the same arrangement.

**Solution:**We can have a O(nlogn) solution by using DP. The details are as follows:

- Sort the presentations by their end time. Thus we will have a sorted array end[N]. N is the number of the presentations.
- Have an array Max_arr[N]. Max_arr[
*i*] stands for if we take end[*i*] as the close time for the conference room, the maximum time the room can be used. It is easy to know that Max_arr[0] = the duration of the presentation that ends at end[0]. We need to find out Max_arr[N-1]. - To calculate Max_arr[
*i*], we first get the start time*si*of the presentation that ends at end[*i*]. Then we do binary search in end[0] ... end[*i*-1] for*si.*Basically we need to find a*j*such that end[*j*] <*si*&& end[*j*+1] >*si*. Therefore, Max_arr[*i*] = max(Max_arr[*i-*1], Max_arr[*j*] + end[*i*] -*si*).

## No comments:

## Post a Comment