CODEWITHSUNDEEP
algorithmsortingtime-complexityintervals
pgiouroukis
pgiouroukis

Reputation: 61

Complement of a set of intervals

I have a set of intervals inside the range [0,k].

How can I produce the complement set of this set of intervals?

I can come up with an algorithm, but it requires sorting the intervals.

Therefore, the complexity is O(nlogn), where n is the number of intervals.

Is there any faster algorithm to do this? If not, is there any way to prove that this is the optimal complexity?

Thank you.

Upvotes: 1

Views: 214

Answers (1)

Damien
Damien

Reputation: 4864

In practice, let us assume that you have found an algorithm to perform this task (find the complement set) in O(n).

Then we can show that you have invented a new sort algorithm working in O(n).

To simplify, let us assume that the array to be sorted consists of natural numbers, and that there is no repetition.

If [a1 a2 ... an] need to be sorted, then consider the intervals [a1, a1+1) [a2, a2 + 1) ... [an, an + 1).

Applying you algorithm to generate the complement set of intervals in O(n), we get n intervals

​ [x1a + 1, x1b) [x2a + 1, x2b])... [xna + 1, xnb)

where the {xia, xib} corresponds to successive aj elements after sorting.

Let us assimilate this relation as a directed edge in a graph, connecting the two vertices xia and xib.

To get the original array in sorted array, we need to find the start of the graph, and then walking through the graph, which can be done in O(n).

The sort has been performed in O(n).

The fact that we did not consider repetitions is not too annoying from a theoretical point of view, if we consider for example that with hashing, we can suppress the repetitions in O(n).

The fact to not consider floating point values is a detail: finding a new O(n) sort algorithm for natural numbers would be already a great result.

Upvotes: 3

Related Questions