# Find the minimum set of intervals for given set of numbers

For any given set of real numbers, find the minimum set of intervals with length 1 that include all elements. For example, for the set: $${\{1.5,2.3,2.4,2.5,2.8,3.3,3.6,3.8}\}$$ the answer is $${\{[1.5,2.5],[2.8,3.8]\}}$$

On the example above $[1.5,2.5]$ is an interval with length $1$ ($2.5-1.5=1$). And there are 2 sets of intervals ($[1.5,2.5]$ and $[2.8,3.8]$).

I need to find the most efficient greedy algorithm for this problem with $O(n\log n)$ time complexity.

My thought is to sort the elements in ascending order (using merge sort for minimum time complexity) and then, starting from the first element, use the current element as the lowest limit, and (element+1) as the highest limit.

This has a running time of $O(n\log n + n)$. $n\log n$ from mergesort and $n$ for running through the elements to decide the intervals.

But I can't tell whether this is the most efficient greedy algorithm I can use for this problem.

• Well, $O(n\log n + n) = O(n\log n)$. And "find the most efficient algorithm" is undecidable problem in general. Mar 1, 2018 at 18:40

To show that the problem has a lower bound of $\Omega (n\log n)$, you can reduce the Element distinctness problem to your problem.