Consider the abcissae x1, x2, x3, ... , xn. Make pairs (A,B) for all x(i),x(i+1) such that: A=min[x(i) and x(i+1)] and B=max[x(i),x(i+1)] Now, consider 2 segments (P,Q) and (R,S).

P ---------------------- Q

'R' can lie either within PQ or outside it.

If R lies outside,

R---P--------------Q

S can either lie outside or inside. If S lies inside PQ, then there is an intersection, else there is not.

R---P------S-------Q

or

R-S-P--------------Q

R---P--------------Q---S

If R lies inside PQ,

P -------------R-----Q

If S lies Outside PQ, then there is an intersection, else there is not.

P -------------R-----Q-----S

P -------------R--S--Q

So, it is just 2 cases we have to check, if we make a min/max pair.

The solution is of time complexity O(n^2).