1
$\begingroup$

Given an interval set $X = \{(s_1, e_1), \dotsc, (s_N, e_N)\}$ ordered such that $s_i \leq s_j$ and $e_i \leq e_j$ for all $i < j$ and an integer $b$, I would like to find a maximum sized subset $X' \subseteq X$ such that $\text{end}(X') - \text{start}(X') \leq b$. Here the $\text{start}, \text{end}$ functions are defined to be the start position of the first interval and the end position of the final interval.

A simple $O(N^2)$ solution would be to set $b' = b + s_i$ and scan all elements to see how many fit within the new bound $b'$. However, given the sorted structure of the problem it seems amenable to a fast solution.

First we can built an interval tree and perform the same set of queries as earlier, but result in an $O(N \log N)$ runtime.

I am curious if this is still suboptimal given that the data already are sorted. Is there a linear time dynamic programming solution?

$\endgroup$
2
$\begingroup$

A simple double pointer $O(n)$ linear scan suffices. Initialize $i = j = 1$.

  1. Increment $j$ until the next step would make $e_j - s_i > b$. Check if $j - i$ is better than the best found result, if yes, store $(i, j)$ (the boundaries of your subset).

  2. Increment $i$. Terminate if we reached the end of the set.

The key observation here is that if a certain $j$ for $i$ is optimal, then for $i' = i+1$, it must be that $j' \geq j$, so we only ever have to scan forwards.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.