1. The Problem
Given a set of `m` points `{x_1, x_2, ..., x_m}` on the real line, we need to find the smallest number of closed unit-length intervals (i.e., intervals of the form `[a, a+1]`) that are needed to cover all the given points.
2. The Idea: Greedy Algorithm
The problem can be solved optimally using a greedy approach. The key insight is that to be as efficient as possible, each interval we place should cover as many *new* points as it can.
First, sort the points in increasing order. The greedy strategy is to take the first uncovered point `x_i` (which will be the smallest one) and place an interval that starts exactly at `x_i`. This interval will be `[x_i, x_i + 1]`. This is the best possible placement for an interval covering `x_i` because shifting it to the left would fail to cover `x_i`, and shifting it to the right would cover the same set of already covered points but potentially fewer points to its right. We then repeat this process, finding the next uncovered point and placing a new interval starting at it, until all points are covered.
3. The Algorithm
- Sort the input points `X = {x_1, ..., x_m}` in non-decreasing order.
- Initialize `count = 0` and `i = 0` (an index for the sorted points array).
- While `i < m` (while there are still uncovered points):
- Increment the interval `count`.
- Let the start of the new interval be `start = X[i]`.
- The interval covers all points up to `start + 1`.
- Move the index `i` forward past all points covered by this new interval. That is, while `i < m` and `X[i] <= start + 1`, increment `i`.
- Return `count`.
4. Complexity Analysis
- Time Complexity: O(m log m)
- The dominant step of the algorithm is sorting the `m` points, which takes O(m log m) time. The subsequent pass through the sorted array takes O(m) time. Therefore, the total time complexity is O(m log m).
- Space Complexity: O(1) or O(m)
- If the sorting is done in-place, the space complexity is O(1). If a copy of the array is made for sorting, it is O(m).