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[0] for each compartment.
Implementation was tricky - times were up to 10<sup>9</sup> (so not possible to use array for DP), but N is up to 10<sup>5</sup>, so at most 2 * 10<sup>5</sup> different times. My first idea was to do "normalization" -> map those at most 2 * 10<sup>5</sup> 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][1] for details and ask if something is unclear...
[1]: http://www.codechef.com/viewsolution/3232355