Butskhrikidze's blog

segments
By Butskhrikidze, history, 6 years ago, In English

given $$$n$$$ segments $$$[l_i, r_i]$$$ where $$$-10^9 \leq l, r \leq 10^9$$$. we are given $$$q$$$ query. each query characterized by one integer $$$x$$$. for each query we must determine how many segment involves $$$x$$$ and detect segments itself by its number. How to solve this problem?

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

»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

If I understand the question correctly we can use the following offline approach:

for each segment [l,r] store it as pair <l , -1> and <r , 1>. for each query store point as pair <x, 0> in the same vector / array.

Sort this structure and maintain a count of currently active segments by adding 1 on <t, -1> entities and subtracting 1 on <t, 1> entities. Answer for each <t, 0> entity is number of active segments.

Could you clarify what you mean by "detect segments itself by its number". If this means listing all segments corresponding to a query then output itself can be $$$O(NQ)$$$ big in worst case.

→ Reply