Andrei Alexandrescu Wrote: > This is somewhat OT but I think it's an interesting problem. Consider > the following data: > > double[][] a = > [ > [ 1, 4, 7, 8 ], > [ 1, 7 ], > [ 1, 7, 8], > [ 4 ], > [ 7 ], > ]; > > We want to compute an n-way union, i.e., efficiently span all elements > in all arrays in a, in sorted order. You can assume that each individual > array in a is sorted. The output of n-way union should be: > > auto witness = [ > 1, 1, 1, 4, 4, 7, 7, 7, 7, 8, 8 > ]; > assert(equal(nWayUnion(a), witness[])); > > The STL and std.algorithm have set_union that does that for two sets: > for example, set_union(a[0], a[1]) outputs [ 1, 1, 4, 7, 7, 8 ]. But > n-way unions poses additional challenges. What would be a fast > algorithm? (Imagine a could be a very large range of ranges).
My first thought was to throw everything in a heap map with key=r.front and value=r That makes each pop operation O(log(# non-empty ranges)) which should be near optimal. > Needless to say, nWayUnion is a range :o). > > Finally, why would anyone care for something like this? > > > Andrei
