I tried the same approach after finding an article on Interval scheduling at wiki.
To maintain all stuff sorted, I completely ignored the value of K and managed a map mapping compartment value to a set containing all input values of entry and exit time.
Although first solution could have passed, I kept on optimizing it after TLEs only to realize the input data is so large that I need to read input fast.
Two similar codes(almost), one getting RUNTIME error & the other got AC
first i submitted using vector (i have done this earlier in other problems successfully ) but got runtime error & same code i submitted using structure(everything was same except i stored the value in struct variable instead of vector ) & … got AC . lol !!
I am trying to solve Bon appetit problem from Jan challenge 2014 from 6 days.Still couldn’t solve it out… So it would be really nice if someone could help me to solve out this. I am trying to solve it in the following way.
1.Sort customers according to departure time.(quicksort)
2.Then go through each customer and directly retrieve a recent customer in that compartment.
if it results in an overlap(discard the customer).
else
increment count and update the recent customer in the specified compartment.
I came to know that a hashmap would serve the purpose.Each compartment would be mappped to certain index by the hashing function and then we would directly go there.
Questions.
1.How can i build a hash function so that given a compartment it would map it to certain index and when again a customer of this compartment appears i would directly go to this compartment in 1 operation.
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