Optimizing for maximum intervals given a distance bound

Question

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?

Answer 1

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.