Dynamic Programming On Intervals

2
votes

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 }

1
algorithmdata-structureshashtable
Please add some example of input and expected output of your question. – samabcde
Can you explain more what's wrong with the naive approach. For me it is O(N) and does not depend on the length of intervals. Am I wrong ? – Ayoub Omari
@Sarmon: the question is how to optimize this for multiple queries. – Doc Brown

1 Answers

0
votes

I would solve this problem the following way.

First I would introduce another array of data structure of the form:

[(ai,bi,ci)]

where

ai - interval start
bi - interval end
ci - count of intervals of original sequence hitting interval [ai,bi]

ai < bi
a(i+1) = bi

so this new data structure covers whole range of original structure, it is increasing and it has the desired count of original interval.

Now to find the count we only need k and perform some kind of binary search to find the interval.