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.
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.
print q space-seperated integers denoting the answer for each of the q non-special integers.
1<=q<= 5 * 10^4
3 2 1
Time Limit 1 second