I have read many answers already written on forum that Why sorting with starting time will give correct answer and sorting with finishing time(as we normally do in activity selection problem) will give WA. Couldn’t really understood the logic till now.
Can anyone explain the logic clearly with the test case where both the logics will conflict?
Thanks!
Hi,
I have used by sorting with the starting time. I had no idea that this can also be solved by sorting with the finishing time as well. I tried many test cases and it passed all test-case by using the sorting with the finishing time. But this:
(start time,end time): (1, 6), (2, 5), (5, 8), (6, 7)
By sorting it by end time: (2,5), (1,6), (6,7), (5,8)
Assigning it to ‘C’ or ‘J’ is failing for me. I hope it removes some part of your doubt. But I am not satisfied completely.
Would be very much happy to know more on it.
Thanks.
thanks for the testcase!
Question can be solved in two parts
to check if it is possible we can use max. overlapping intervals(or use hotel booking problem where no of rooms is 2) if max overlapping is 2 or less than 2 it is possible ,if not it is not possible.
to assign sort according to start time
ex
C_________________C C_____________________C (C/J)____(C/J)
J______J J_____________J J ________J
hope this will help
It can be solved even if you sort by end time.
Afaik most people failed the test case where J and C are both available for job and thus they assigned the job randomly. Instead if they both are available then we should the one with higher ending time.
Taking example from above comment, if you give first job to C and second to J, then you have J and C available for third job. C is busy upto 5 and J upto 6. Hence we choose J because we need the earlier time of 5 incase any layer job has lower start time.
Hope you understood.
Check out this detailed solution of Codejam 2020.