3
$\begingroup$

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.

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

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the answer, but my question is whether there is a greedy algorithm that gives a better solution while having O(nlogn) at the same time, not how to improve the time complexity of the algorithm I thought.. $\endgroup$
    – Pantelis
    Mar 1, 2018 at 1:14
  • $\begingroup$ @Pantelis, I'm confused. The question asks for "the most efficient" algorithm. How would we know that you don't care about efficiency, and only care about a better solution? And I'm not sure what better means. Please edit the question to make it a lot clearer what you are asking. As it stands, this looks to me like a valid answer to the question that is asked at the top. $\endgroup$
    – D.W. ♦
    Mar 1, 2018 at 5:25
  • $\begingroup$ Maybe what you want is how to prove the correctness of your algorithm, that is, your algorithm always find the optimal solution. In this case, it is a typical method for greedy algorithm: showing your first decision is correct. That is, there is an optimal solution with end-point at the smallest number. It is very similar to the "activity selection problem" that can be found in Wiki. $\endgroup$
    – Bangye
    Mar 1, 2018 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.