My solution for this question is giving WA for 1st and 2nd testcase in the 3rd subtask. Can anyone please explain why?
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:
Consider:
[2,10]
[3,4]
[5,6]
You sort by end:
[3,4]
[5,6]
[2,10]
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.