My solution did not get accepted because TLE. (I used JAVA)
Here is the code for that solution.
But now i canged the data type values. (I used long data type and i changed them to int) Then my code got accepted. Here is that accepted code.
(This is not a problem in the algorithm i suppose, The code is almost same, I think to overcome the TLE problems we should aware of these kind of problems too Changing data types will get you accepted I would really like to know why this is happening )
Even O(K) will be slow, so O(K log(K)) and O(K^2) are slow too… But similar to my approach, there are customers for at most N compartments, so you have to take care only those only…
Just try to replace your for(int i=0; i<k; i++) { with map iterator, same for next for loop
Basically, my algo was as follows:
Sort the customers segregated by first the compartments, then by their arrival time. Hold one customer with us,start by the first customer :
If the next customer needs a different slot(all requests for current slot is done) accept the one with us and hold on to the new one.
Else, if the next customer arrives after the customer with us would leave - we can cater to the customer with us. So increment the count and hold the new customer now.
Else, if the next customer can leave earlier than our current - shoo away the current and keep the new one.