Consider the sorted intervals one by one, add it if it is possible (only need to check the last select interval and the current one).
The intuition of this greedy is that, we need to make sure the space remained for the later intervals is as large as possible. The proof is also easy. For the first interval, we definite choose the interval which ends earliest. Otherwise, we can replace the first interval in the best solution with that earliest ended interval (with at least same best solution). Therefore, we can achieve the maximum interval selections with choosing the earliest ended interval. Recursively, we can see that the greedy is correct.
In summary, we can solve this problem in O(N log N), where N is the total number of intervals in all sets.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
I have sometimes problem with greedy algorithms, because sometimes its not easy to see if it works or not… From my point of view the DP is more “deterministic”.
The key idea is that compartments are independent as written in editorial.
You can use this DP:
for max to time MT, we know that max guests starting at MT + 1 is 0
for all times T = MT downto 0 we can do: if there comes guest at time T and leaves at time L, the max for time T is max( T + 1, 1 + dp[L] )
at the end the result is dp for each compartment.
Implementation was tricky - times were up to 109 (so not possible to use array for DP), but N is up to 105, so at most 2 * 105 different times. My first idea was to do “normalization” -> map those at most 2 * 105 different times to numbers 0…200000 and use array for DP (a lot of work needed here), but than I made it using tree maps - see my Java solution for details and ask if something is unclear…
I’ve used the same approach given in the editorial but I thought of it as Earliest Deadline First(EDF) scheduling, allot a compartment to the customer who leaves earliest And in order to keep track of free/occupied compartments I used map, using compartment number as key and the leaving time as data. STL sure makes programming in C++ a lot simpler. Here’s my solution.
@shangjingbo i just wanted to know what’s wrong in the solution here. In this i sort the array two times. First i sort it with respect to “room no” then in the chunks of same room no’s i sort them wrt deadlines. At least can you tell me which test case does it fail. Please help