Number of Ranges that lie completely in a particular Range
Let us say we have n ranges each specified by
[l_i,r_i] where 1<=i<=n
And we have a query of type [L,R] in which we have to find the number of
ranges among those n ranges that lie completely in the given range i.e.
[L,R]
Example:
n ranges are:
here n is 2.
2 4
3 3
for query 3 5, output should be 1.
for query 2 5 output should be 2.
I know method for O(m*n), where n is number of ranges and m is number of
queries, but feels like there must be a more efficient implementation.
No comments:
Post a Comment