Given a set S of N horizontal segments in the 2-D plane. Return will there exist a line which intersects all the segments in S.
A segment is represented as a pair of coordinates of its left and right end point. A line intersects a segment if it intersects the line segment defined by the two endpoints of this interval.
We have to tell about the existence, the line is not required. Expected complexity is O(n). See a example figure below. Note that the transversal may not always be vertical as shown.