Editorial for DMOPC '15 Contest 3 P1 - Quality Scenes - Olympiads Online Judge

Editorial for DMOPC '15 Contest 3 P1 - Quality Scenes

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Consider sorting the video clips and, subsequently, their endpoints, $a$ $a$ , $b$ $b$ , $c$ $c$ , and $d$ $d$ :

If $a > c$ $a > c$ , swap $a$ $a$ and $c$ $c$ and $b$ $b$ and $d$ $d$ ; otherwise, do not swap anything.

Now, we can check if the endpoint of the leftmost video clip (starts at $a$ $a$ and ends at $b$ $b$ ) overlaps with the rightmost video clips (starts at $c$ $c$ and ends at $d$ $d$ ):

If the start of the rightmost video clip ( $c$ $c$ ) is less than the end of the leftmost video clip ( $b$ $b$ ), they must overlap, so output YES; otherwise, output NO.

Time Complexity: $\mathcal{O}(1)$ $O (1)$

Bonus: How would you solve this problem if there were $N$ $N$ video clips?

Comments

There are no comments at the moment.