You are a given an array of contiguous intervals i.e. { [a,b],[b,c],[c,d],...,[g,h],[h,i] }
Given a query of type n m k, we need to output the number of intervals between n,m (inclusive, 1-based indexing) containing k.
My Approach : ( Naively check for all the intervals between n,m and keeping a counter. )
This works if m-n and number of queries are small, but this would be really inefficient for larger values of n,m and multiple queries.
So I was thinking of a Dynamic Programming approach such that we can save number of intervals containing z upto an interval numbered say x in the array dp[x][z], then I can answer any query n m k as dp[m][k]-dp[n][k]. But this also fails if intervals given in the array are too large as it would take greater time to construct the dp array.
How do I get around this or is there a simpler approach that I am missing?
Any hints would be helpful.
Example :
Array : { [1,3],[3,2],[2,1],[1,5],[5,3] }
Queries : { 1 2 2 } , { 1 3 3 } , { 2 2 4 }
Output : { 2 } , { 2 } , { 0 }