You are not logged in. Please login at www.codechef.com to post your questions!

×

FGFS - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vivek Hamirwasia
Tester: Mahbub
Editorialist: Jingbo Shang

DIFFICULTY:

Easy

PREREQUISITES:

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.

This question is marked "community wiki".

asked 13 Jan '14, 15:11

shangjingbo's gravatar image

3★shangjingbo ♦♦
161446376
accept rate: 0%

edited 22 Apr '15, 17:35

admin's gravatar image

0★admin ♦♦
19.8k350498541

1

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

(13 Jan '14, 15:33) betlista ♦♦3★

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

(14 Jan '14, 11:22) ajit_a2★

I think it should be caused by different implementation. STL is always a little slower.

(15 Jan '14, 12:10) shangjingbo ♦♦3★

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

link

answered 13 Jan '14, 15:18

bugkiller's gravatar image

3★bugkiller
8.7k194898
accept rate: 9%

edited 13 Jan '14, 15:46

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

(13 Jan '14, 15:30) betlista ♦♦3★

Probably due to the doubled time limit for Java?

(13 Jan '14, 15:35) bugkiller3★

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

(13 Jan '14, 15:56) sumitb2★

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

(13 Jan '14, 16:00) betlista ♦♦3★

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

(13 Jan '14, 16:06) bugkiller3★

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

(13 Jan '14, 17:39) f03nix2★

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.
(13 Jan '14, 17:42) f03nix2★

@f03nix >> Nice implementation :)

(13 Jan '14, 17:56) bugkiller3★
showing 5 of 8 show all

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

link

answered 13 Jan '14, 15:45

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

edited 14 Jan '14, 01:06

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

(13 Jan '14, 15:48) bugkiller3★

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.

(13 Jan '14, 19:05) shangjingbo ♦♦3★

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)

(13 Jan '14, 22:55) cyberax ♦3★

Shouldn't it be dp[T]=max(dp[T+1],1+dp[L]); ??

(16 Jan '14, 19:04) h1h33★

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

link

answered 13 Jan '14, 16:06

kuruma's gravatar image

3★kuruma
17.7k72143209
accept rate: 8%

2

Good to see you playing with the STL. Cheers!

(13 Jan '14, 16:10) bugkiller3★

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

(13 Jan '14, 16:17) kuruma3★

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

My approaches:

http://www.codechef.com/viewsolution/3205739 http://www.codechef.com/viewsolution/3205773 http://www.codechef.com/viewsolution/3206699 http://www.codechef.com/viewsolution/3249418

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

(13 Jan '14, 16:30) hrculiz1★

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<values=""> > 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

(13 Jan '14, 16:34) kuruma3★

Will you please help me checking why am I getting WA for the problem. http://www.codechef.com/viewsolution/3256692

(15 Jan '14, 09:40) hrculiz1★

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

(17 Jan '14, 20:13) kuruma3★
showing 5 of 6 show all

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.

link

answered 13 Jan '14, 17:42

thewanderer's gravatar image

2★thewanderer
9128
accept rate: 0%

@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

link

answered 13 Jan '14, 17:48

paramvi's gravatar image

3★paramvi
165
accept rate: 0%

edited 14 Jan '14, 21:30

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

link

answered 13 Jan '14, 18:58

anhtuann's gravatar image

3★anhtuann
1
accept rate: 0%

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.

link

answered 13 Jan '14, 19:10

mjbpl's gravatar image

5★mjbpl
41927
accept rate: 6%

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

link

answered 13 Jan '14, 19:15

sagar55's gravatar image

4★sagar55
13
accept rate: 0%

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.

(14 Jan '14, 16:36) mjbpl5★

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

link

answered 14 Jan '14, 10:46

anonymousins's gravatar image

2★anonymousins
29682122
accept rate: 11%

edited 14 Jan '14, 17:00

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

(14 Jan '14, 11:29) michelangelo4★

but is my approach correct and if it is how to implement it?

(14 Jan '14, 14:40) anonymousins2★

@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! :D STL map takes care of hasing, I read that its insert, delete and lookup operations are of O(logn) complexity.

(14 Jan '14, 22:30) thewanderer2★

how can we do it in c?

(15 Jan '14, 11:35) anonymousins2★

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.

(15 Jan '14, 18:01) thewanderer2★

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

Can anybody explain why this is happening.

thanks in advance :)

link

answered 14 Jan '14, 12:00

vidudaya's gravatar image

3★vidudaya
12
accept rate: 0%

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

link

answered 17 Jan '14, 19:37

code_overlord's gravatar image

3★code_overlord
2236
accept rate: 0%

I got runtime error please help me .solution id: https://www.codechef.com/viewsolution/9963237.

link

answered 23 Apr '16, 17:53

vickycod's gravatar image

2★vickycod
21112
accept rate: 6%

link

answered 17 Oct '16, 02:39

adi_1996's gravatar image

4★adi_1996
2115
accept rate: 0%

https://www.codechef.com/viewsolution/14299209

What's wrong with the approach? Please help

link

answered 20 Jun '17, 23:16

apurva_121's gravatar image

2★apurva_121
1
accept rate: 0%

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

Thanks a lot for giving your time.

Here is my code.

link

answered 16 Jul '18, 13:56

samarth1402's gravatar image

3★samarth1402
101
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×3,820
×1,024
×801
×51

question asked: 13 Jan '14, 15:11

question was seen: 14,273 times

last updated: 16 Jul '18, 13:56