gsmcoder97's blog

Finding elements in segments
By gsmcoder97, history, 8 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

  1. sort elements in all n segments

  2. when query comes, sort the query array

  3. check each segment if the query belongs to it

  4. return to 2

You can check in way like this:

  1. ps:=first element of segment, pq:=first element of query

  2. if (pq out of range) return true;

  3. if (ps out of range) return false;

  4. if (ps == pq) ps and pq move to next;

  5. else if (ps < pq) ps move to next;

  6. else return false;

  7. return to 2

→ Reply