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)$ ~\mathcal{O}(1)~

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

Comments

There are no comments at the moment.