Whats the fastest way to get range complement? [duplicate]

This question already exists: Closed 11 years ago.

Possible Duplicate:

Fastest way to get range complement

I h开发者_JAVA百科ave a sorted array of nonoverlaping ranges for example (0,2],(2,4],(6,9] and I wish to get it's complement with (0,12] which shoud return (4,6],(9,12] .Whats the fastest way to do that?

---

Assume your input data is an array of this form:

{ 0, 2, 2, 4, 6, 9 }

Simply add the new elements 0 and 12 to the beginning and end, and you have

{ 0, 0, 2, 2, 4, 6, 9, 12 }

And reinterpreting consecutive pairs as intervals, you have:

• (0, 0]
• (2, 2]
• (4, 6]
• (9, 12]

The fact that you have degenerate intervals makes this something of a mess, but if your original list did not have any degenerate intervals, your output list would not either.

Depending on the format of your data and whether you can do in-place modification, this operation may be O(1).

---

I think it takes O(n) assuming n as the size of the sorted array. Because you should check the gap between every adjacent ranges.

P.S. I guess it is your homework!

---

• create one list of 2*n numbers. {a[0] .. a[2n-1]} by merging all intervals. It's sorted by construction.
• ignore the pairs (a[i], a[i+1]) where i is odd and a[i]==a[i+1].
• put at the front the lowest possible value.
• put at the back the highest possible value.
• splice two by two, you obtain the complement.