Greedy Interval Covering of Sorted Points

Reported in interviews at Bank of America

Problem statement

You are given $n$ points $x_1 \leq x_2 \leq \cdots \leq x_n$ on the real line and a fixed interval length $L > 0$.

  1. Design an $O(n)$ algorithm that outputs the minimum number of closed intervals of length $L$ needed to cover all $n$ points, along with the intervals themselves. Several optimal placements can exist, so report the canonical greedy one: anchor each new interval at the leftmost still-uncovered point $x$ (it covers $[x, x+L]$), skip every point $\le x + L$, and repeat.
  2. Prove that your greedy choice is optimal.
  3. Describe how your algorithm handles edge cases: clusters of points within distance $L$, ties (duplicate point values), and single-point inputs.

Graded function: min_interval_cover(points, L) returns [count, starts], where starts lists the left endpoints of the greedy intervals in increasing order (interval $k$ is $[\text{starts}[k], \text{starts}[k] + L]$).

Examples

min_interval_cover([], 1.0) -> [0, []]
min_interval_cover([1, 2, 3], 1) -> [2, [1, 3]]
min_interval_cover([0.5, 1.0, 2.0, 4.0, 4.5], 1.5) -> [2, [0.5, 4.0]]

In the second example $[1,2], [2,3]$ is also an optimal cover, but the greedy anchors the first interval at $1$ (covering $1$ and $2$) and the second at $3$, the leftmost point still uncovered.

Show hint

If some interval must cover the leftmost point, where is the least wasteful place to put it?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems