As my previous post was removed because of the discussion being carried out in the time of the contest. This is my approach
- sort jobs according to start time
- initialise end times of Cameron and Jamie to 0 and 0 indicating they aren’t busy
- Take one job from the sorted array and compare its start time with the end time allocated to the boy, if it is less than that then i.e. he is busy. Do a similar check for the girl. Even if she is busy then you can declare it as “impossible”.
- If they are not the job is allocated to the concerned partner (boy or the girl) and the same is marked in the original input (i.e. the allocation ‘J’ or ‘C’). The end time of that partner is now updated to the end time of the job they have been just allocated.
- Keep enumerating through the sorted array until you have allocated all jobs or have declared the scheduling impossible.
- At the end concatenate the letters (in order) from step 4 corresponding to the actual input which will be the final solution.
I tried this approach using a dictionary with the job (s,e) as the key and the value which is its position in the original input. In this way we won’t run into non - deterministic behavior of Python dictionaries since the elements remain intact although their order may change in between.
I tried this on my editor (where it gave the expected solutions to the sample cases) and then I ran the sample tests on code jam editor where also I got the expected output.
However, as soon as I submitted it started giving me RE (run time error) in every case. Can anyone give the reason?