Edit: I tried this solution to reduce the time taken, but again it gives WA for 1st and 2nd testcases in the 3rd subtask and for the 2nd and 3rd testcases in the 4th subtask.
I’m not sure if your collision detection and handling is correct:
You sort by end:
1 and 2 do not collide (according to your logic, in reality they do)
2 and 3 collide: Collision is set to 1 and you record the collision between 2 and 3
That is the end of collision detection.
Then you look for a gap big enough too fit the whole interval 2 or 3. But you should only look for a shift of interval 3, because it also collides with 1. Shifting 2 will not lead to a valid solution.
Hmmm… So, If I sort by start, will it give AC for the third subtask?
No this will have same problem at different tests. You need to find a way to recognize these cases and handle them.
Is it possible for you to provide a hint? Thanks!
Later when I’m home
Sure, take your time!
The unofficial editorial is ready, you can check it.