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.

Author: FatalEagle

Knowledge required: simple logic

This problem asks whether two given video clips overlap. In other words, it cares if | \{x \in \mathbb{R} \mid a \le x \le b\} \cap \{x \in \mathbb{R} \mid c \le x \le d\} | > C for any constant C.

solve :: [Integer] -> String
solve [a,b,c,d] | a > c = solve [c,d,a,b]
solve [a,b,c,d] | b > c = "YES"
solve [a,b,c,d] = "NO"
main = interact $ solve . (map read) . lines

Time Complexity: \mathcal{O}(1)

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


  • 0
    Riolku  commented on July 21, 2019, 1:55 p.m.

    That is Haskell.

  • 2
    ghost  commented on July 21, 2019, 7:59 a.m.

    What language is this?