How to solve this inteview problem

Revision en2, by saint_coder, 2019-06-21 10:37:13

I couldn't solve this. Please do tell me any simple approach which can pass the time constraint.


You are given n intervals which are termed as special intervals. Each interval is of a different type.

Again, you are given a set of q non-special intervals. For each non-special interval in the given q intervals, you have to find the number of different types of special intervals in that non-special interval.

Note: A special interval is inside a non-special interval if there exists a point x which belongs to both special interval and non-special interval.

Input format

First line: n denoting the number of special intervals

Next n lines: Two integers denoting lspecial[i] and rspecial[i] denoting the range [l,r] for the ith special interval.

Next line: q denoting the number of non-special intervals

Next q lines: Two integers denoting lnonspecial[i] and rnonspecial[i] denoting the range [l,r] for the ith non-special interval.

Output format

print q space-seperated integers denoting the answer for each of the q non-special integers.





1<=q<= 5 * 10^4



Sample Input


1 2

1 5

1 7


1 3

3 3

6 7

Sample Output

3 2 1

Time Limit 1 second

Tags #interview, #problem, interval


  Rev. Lang. By When Δ Comment
en2 English saint_coder 2019-06-21 10:37:13 16
en1 English saint_coder 2019-06-21 10:36:27 1425 Initial revision (published)