FGFS - Editorial



I have used map data structure, coupled with fast I/O and good code organization and got AC with relative ease.

If you know the algorithm and some good data structures, using scanf()/printf() is almost always enough!

As a bonus, if you know your way around how the I/O system works, you can even get AC with cin/cout as my solution submitted few seconds ago in practice section proves:


Think algorithmically above all,

Bruno :slight_smile:


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 :slight_smile: 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


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


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 :slight_smile: ) 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 … :slight_smile:


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).

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.


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…


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 :smiley: Changing data types will get you accepted :smiley: I would really like to know why this is happening )

Can anybody explain why this is happening.

thanks in advance :slight_smile:


Can someone explain the time complexity given in the editorial? Does it take the time taken to sort the intervals into account?


I got runtime error please help me .solution id:




Can someone please point the errors



What’s wrong with the approach? Please help


I am getting TLE. Can someone please find the reason.

Thanks a lot for giving your time.

Here is my code.


Hm? I was able to do that in Java and had no problem with TLE (but I used DP)…


“exclusive at two ends”, it was left closed and right opened [from, to ) but probably it changes nothing…


Probably due to the doubled time limit for Java?


“times were up to 10^9 (so not possible to use array for DP), but N is up to 10^5” Exactly! This was the area that required to be hit in the problem.


My sol. was getting TLE due to sort function. http://www.codechef.com/viewsolution/3250997

But I have seen some sol. using the same approach and getting accepted. Can you explain the flaw in my sol.?


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 :wink:


@betlista >> Ofcourse, that would never go 10^9 iterations. Damn! :frowning: :smiley: