Re: [OT] n-way union

[Sean Kelly]

I have a better idea which is pretty much in line with the heap-based 
solutions already posted.  Place all the ranges in a min priority queue 
where the priority of a range is equal to the value of its top element. 
 Pop the value off the heap at the front of the queue.  If the heap is 
empty then remove it.  If it contains more elements then fix up the 
priority queue to restore the invariant (since the priority of the head 
range may have changed).  The temporary space would just be of size N 
where N is the number of ranges, and the number of duplicate compares is 
minimized.