Count the number of intervals that fall in the given range Let me explain the question suppose there are Range [1,10] and the provided intervals are (1,3),(1,8),(2,4),(2,5),(2,3),(3,9),(3,8),(3,6)   and ask to find out the number of intervals that fall'a between the ranges [1,5] the answer is 4. These are four  [(1,3),(2,4),(2,5),(2,3)] intervals that fall's in the range [1,5]. same as if there are Range[1,N] and i provide you the intervals ,then how to find out that how many intervals are in the given range. in O(logn) Complexity or better than this ?
 A: You can build the interval tree of the input intervals. Following, you can execute a range query (i, j) that returns all intervals that overlap with (i, j)
in O(logn + k) time, where k is the number of overlapping intervals, or a range
query that returns the number of overlapping intervals in O(logn) time.
A: You can do it in O(log n) as follows, using two binary searches per query. 
PRE-PROCESSING:
1. Add the end point of each interval to a list called pos_end. pos_end should initially contain -1 as a dummy element (assuming all interval end points are positive).
2. Add the start point of each interval to a list called pos_start.
3. Sort pos_start and pos_end if they are not already sorted.
QUERY:
Let [L, R] be the range you are querying. The answer (number of all intervals that are completely contained by [L,R]) is:
lower_bound(R, pos_end) - upper_bound(L, pos_start) lower_bound(x, pos) returns index of first element in array pos that is smaller than or equal to x. 
upper_bound(x, pos) returns index of first element in array pos that is greater than or equal to x.
All you have to do is  to implement the lower_bound and upper_bound functions using binary search. The std functions in C++ with the same names don't return exactly same values as those described here.
