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!
I interpret the question this way (and if I've misinterpreted, kindly ignore this answer): you have $n$ inequalities of the form $$a_i\le x\le b_i$$ and you want to know whether there is an $x$ that satisfies at least $k$ of them. If there is such an $x$, then there is an $a_i$ that satisfies $k$ of them (there's also a $b_i$ that satisfies at least $k$ of them), so all you have to do is check each of the $a_i$ to see if it works.
Well, this reduces it to a finite problem, thought whether it is fast enough for your purposes, let alone optimal, I cannot say.