[Solved]: Lines intersections with a point in 1D

Problem Detail: 

I have an array of lines in 1D represented by coordination and weight, it can be only positive weight. I want to find all the lines that intersect a point in a given range.

Is there any efficient way of doing it?

Asked By : Ilya_Gazman

Answered By : G. Bach

You can do the trivial scan in $\mathcal{O}(n)$ time where $n$ is the number of intervals (just check for each interval whether your value is in it) or you can use an interval tree; those allow for querying in logarithmic time, see for example here.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16570