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
