I have been solving some problems recently and they tend to have the following query at the end:
Given n segments a1,a2
b1,b2
.
.
.
And some numbers of an array x1, x2, x3, . . .
I want to find the segments in which each of these numbers appear. There might be more than one segment so I want all the segments in which they appear.
How do I approach this question?
Thank you.
sort elements in all n segments
when query comes, sort the query array
check each segment if the query belongs to it
return to 2
You can check in way like this:
ps:=first element of segment, pq:=first element of query
if (pq out of range) return true;
if (ps out of range) return false;
if (ps == pq) ps and pq move to next;
else if (ps < pq) ps move to next;
else return false;
return to 2