Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

### hello_hell's blog

By hello_hell, history, 2 months ago, ,

In this problem i sorted the activities by their ending time. With this solution i got Wrong Answer 6 times. I got so much frustrated that i implemented this brute force solution & even it gave me a wrong answer. Would you please point out my mistake.

• -11

 » 2 months ago, # | ← Rev. 3 →   +1 Does your code handle this case ?21 21 2for this case, your first solution is giving this output : JJ ( which is wrong ), the correct output must be either CJ or JC
•  » » 2 months ago, # ^ |   +1 explain ur case in a bit more detail.
•  » » 2 months ago, # ^ |   0 yes
•  » » » 2 months ago, # ^ |   0 Check again, I have edited my comment.
•  » » » » 2 months ago, # ^ |   0 yes my code (brute force one) works fine , i also figured out this testcase.
•  » » 2 months ago, # ^ |   0 yes i think, end time time sorting order should give AC for this test case.
 » 2 months ago, # |   0 i sorted it by start time and it worked. Sorting by start time is correct. But I couldn't think, why sorting by end time is giving wrong answer.
 » 2 months ago, # |   0 Check for the multiple occurrences of same time activities.
•  » » 2 months ago, # ^ |   0 what do u mean by same time activities?
•  » » » 2 months ago, # ^ |   +1 let's say Activity A occurs at [1 , 10] , Activity B also occur at same time i.e. [1 , 10]. Then in that case we have to print "CJ" or "JC" as our answer;
 » 2 months ago, # |   0 I am not sure how your code is supposed to work.I implemented event based solution. Every activity start is $1$ event, every end a $-1$ event. Sort events by time.Put the two persons on a stack. For every start event, pop a person, for end event push the person used before for that activity.Every push contributes to the answer. If you need to pop but there is no person on the stack then there is no solution.
•  » » 2 months ago, # ^ |   0 u also went in order of start time sorted order.
•  » » 2 months ago, # ^ |   0 this seems similar to maintaining two pointers and move forward the pointer which is less then or equal to current event's starting time. if you find there is no pointer with such condition then there exit no solution.
 » 2 months ago, # |   +1 Greedy works if you sort by the starting time of each activity. Your program will say that "something is wrong" for this testcase: 1 4 0 200 50 100 150 300 250 270 When solving this problem, my first idea was to check for bipartite graph, so I stuck with it. The analysis of the problem is already available on the link you posted.
•  » » 2 months ago, # ^ |   0 thanks , but brute force solution works for this testcase.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +2 Brute-forcing would be testing every possible division of activities. The second code you linked is a greedy solution that doesn’t work.Notice that while reading, you attribute the activities in input order, which is not necessarily the best and can be easily broken. Brute-forcing everything should be done in $2^n$
•  » » 2 months ago, # ^ |   0 ya, end time sorting would fail for this test case.
 » 2 months ago, # |   0 I think it is the use of the none_of(begin, end) function. End should be position on after the last, but is not in the code.