Determines the smallest set of unit-length closed intervals that contains all of the given points

Question

Question: Describe an efficient algorithm that, given a set $\{x1, \cdots, x_n\}$ of points on the real line, determines the smallest set of unit-length closed intervals that contains all of the given points.

Attempt: If we sort the points in any order we would like to start with, we will get $S=\{y_1, \cdots, y_n\}$. Next, we pick the smallest each time from $S$ and build a UNIT internal around it, so we have $S-\{smallest(S)\}$ left and the unit interval would be $[y_i, y_{i+1}]$. Keep following this approach would guarantee we cover the whole real line.

Complexity: apply any sorting algorithm to sort points in non-decreasing order. Then take smallest point and build unit interval, so we have $O(n\log{n})$.

Problem: I am not really sure what is the goal behind the question? The mail goal is basically to build unit intervals all across the line? If yes for what purpose (application) please?

Edit: I made a mistake as it should be $[y_i, y_{i}+1]$.

Answer 1

To answer your question:

I am not really sure what is the goal behind the question?

If I were to give this assignment to my students, I would expect

1. An algorithm in pseudo code
2. Running time analysis
3. Proof of correctness

You have given neither.

It is always risky to handwave an algorithm, because you always cherry-pick data structures and details when you analyse it, and the running time you end up with might not actually be realizable.

So: How do you traverse the points, what is the running time, and why is it correct?

---

On the second question, why do we want to cover points with unit intervals, the answer is two-fold:

1. It is a constructed formal problem designed to make you think about algorithms, as a means to practice algorithmic problem-solving more than solving real-world problems. When we do exercises in computer science, these are often "idealized/platonic" versions of problems that are much simpler than real-world problem, simply because real-world problems are messy and contain a lot of noise.
2. One example of a real-world problem could be: there are a bunch of houses along a road, and you want to place mailboxes so that the maximum distance from each house to a mailbox is $\delta$. How many mailboxes must you place and where? Feel free to replace "mailbox" with "fire station", "hospital", "school", etc.
3. A more general real-world instance could be that you have points in the plane, and want to cover all the points with as few radio antennas as possible. Each antenna covers a circle with radius $\delta$. This is a more difficult problem to solve, of course, but when learning a new field, one starts simple and builds on that.