# FGFS - Editorial

Author: Vivek Hamirwasia
Tester: Mahbub
Editorialist: Jingbo Shang

Easy

Sort, Greedy.

### PROBLEM:

Given some sets of open intervals (exclusive at two ends), for each set, find the maximum number of disjoint intervals.

### EXPLANATION:

First of all, we need to observe that the intervals in different sets are independent (in the original statement, the customers preferred in different compartments are independent).

For a single set, it is a classical greedy problem, called Activity Selection problem. The greedy method is as following:

1. Sort the intervals by their right end ascending.
2. Initialized the select intervals as an empty set
3. Consider the sorted intervals one by one, add it if it is possible (only need to check the last select interval and the current one).

The intuition of this greedy is that, we need to make sure the space remained for the later intervals is as large as possible. The proof is also easy. For the first interval, we definite choose the interval which ends earliest. Otherwise, we can replace the first interval in the best solution with that earliest ended interval (with at least same best solution). Therefore, we can achieve the maximum interval selections with choosing the earliest ended interval. Recursively, we can see that the greedy is correct.

In summary, we can solve this problem in O(N log N), where N is the total number of intervals in all sets.

### AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:

Authorâ€™s solution can be found here.
Testerâ€™s solution can be found here.

5 Likes

Very Strict Time Limit! Even with the sort functions removed, it gets a TLE.
Probably because O(k^2) solutions were forced NOT to pass the time limits.

http://www.codechef.com/viewplaintext/3241391

1 Like

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â€¦

1 Like

Probably due to the doubled time limit for Java?

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 109 (so not possible to use array for DP), but N is up to 105, so at most 2 * 105 different times. My first idea was to do â€śnormalizationâ€ť -> map those at most 2 * 105 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 for details and ask if something is unclearâ€¦

1 Like

â€ś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

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

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:

http://www.codechef.com/viewsolution/3251027

Think algorithmically above all,

Bruno

1 Like

Good to see you playing with the STL. Cheers!

2 Likes

Thanks @bugkiller, actually it was the first time I used an iterator to iterate over a map, so I was really happy with it

I was using similar approach, but was new with STLâ€™s, yet got to learn very new things from this question.

My approaches:

finally saw your solution just after completion, liked the way of your coding.

Nice job though, playing with the multimap

Usually, whenever I see a multimap question I always tend to â€śdegenerate itâ€ť into a map of map<key, vector > as it is more intuitive to me.

Regarding your approach, I guess you can separate the multimap from the data structure and thus speed up your code quite considerably

You didnâ€™t even need the k, i used a greedy approach as well and passed within time O(N).

http://www.codechef.com/viewplaintext/3170241

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 :

1. 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.
2. 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.
3. Else, if the next customer can leave earlier than our current - shoo away the current and keep the new one.

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

@f03nix >> Nice implementation