Could you please help me to design the following algorithm:
I have a random-access list of line segments defined by a pair of points $[x^s_i; x^e_i]$. The list is initially unsorted, but of course can be sorted by left or right coordinate in $n \log n$.
I need to determine whether at least $k$ of these segments intersect or not as quick as possible (asymptotically).
Thank you very much in advance!