Wrong answer in Moving Intervals - ZCO 2018

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.

2 Likes

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.

Hmmm… So, If I sort by start, will it give AC for the third subtask?

1 Like

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! :smile:

1 Like

Later when I’m home

Sure, take your time!

1 Like

The unofficial editorial is ready, you can check it.