Could someone post an AC solution in Python ? I don’t even know if it’s possible since no pythonista managed to get AC for this problem. I would love to learn how to solve it
Yes, DP is feasible for this problem. Congratulations for you Accept!
I think greedy is much easier to implement, since we don’t need to remap the times.
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 !!
http://www.codechef.com/viewsolution/3160692 (using vector)
http://www.codechef.com/viewsolution/3160968 (using structure)
i’d appreciate if anyone willing to answer …
I have sometimes problem with greedy algorithms, because sometimes its not easy if it works or not…
Just a comment, in this specific case, the correctness of the greedy approach can be proven.
(cf. the linked wiki page about Activity Selection Problem)
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.
2.Would this approach give me WA or TLE?
Please help…
I have implemented the same method and solution is accepted with 2.02s but I can see solution with similar approach accepted in less than 1s. Is it only because of the fast IO or some other tweak in the code ?
My solution : http://www.codechef.com/viewsolution/3228255
I used radix sort for sorting finishing time and preferred components, and then used the activity selection problem, coupled with fast I/O and got AC. Link: http://www.codechef.com/viewsolution/3235970
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 )
Can anybody explain why this is happening.
thanks in advance
but is my approach correct and if it is how to implement it?
Vectors of vector is extremely time consuming for such large data. POD works better here.
Your struct is supposed to take 3 members at compile time, so it is faster. On the other hand, a vector is generic and ready to accommodate more elements (members) although you don’t supply it.
Plus vector keep track of currently allocated memory and size behind the scene that is more expensive than PODs(more@http://en.wikipedia.org/wiki/Plain_old_data_structure) without any constructor/destructor cost.
@anonymousins read my answer above, I’ve used the same idea. When searching for hash functions I came across STL maps, read about them, implemented them in my code and voila! AC! STL map takes care of hasing, I read that its insert, delete and lookup operations are of O(logn) complexity.
Will you please help me checking why am I getting WA for the problem.
http://www.codechef.com/viewsolution/3256692
how can we do it in c?
I think it should be caused by different implementation. STL is always a little slower.
If you want to do it in C you’ll have to write your own code, but I suggest you start using C++ with STL, C++11 library is huge and its also the standard.
Shouldn’t it be dp[T]=max(dp[T+1],1+dp[L]); ??
Can someone explain the time complexity given in the editorial? Does it take the time taken to sort the intervals into account?
hello the main differences I can see between both of our solutions is the type used to store the answer… I’ve used long long
EDIT: After changing the data types I now get TLE veredict with your code… Try to encapsulate the main procedure to get the answer on a separate function… It’s easier to debug and spot bottlenecks