I have $k$ lists that I would like to combine to a single list. Each list's elements are unique and are sorted in a particular order, but there is no notion of an absolute order, and different items across lists can only be compared if they are equal. To give a specific example (here I use $<$ to indicate the sorting inside each list):
l1 = a < b < c l2 = b < d
l1 + l2 should result in one of the following (and I don't care which one it results in):
a < b < c < d a < b < d < c
If the lists are incompatible, e.g.
a < b and
b < a then I want to get an error. The resulting list (if it exists) should respect all of the orderings of the sublists. Also all the items should be unique in the result.
I thought about modifying k-way merge somehow but it's not clear to me how to do that without a global order. By the way, I'll probably be happy with a $O(nk)$ solution.
Perhaps a better way to phrase the problem is this. I'd like to construct an order vector given $k$ pieces of that order vector (or get an error if that's impossible).
Here's an algorithm that I think works for $k=2$. Find and mark all the duplicates - I think this is $O(n)$ - then start writing down elements from first list until you hit a duplicate, once you do add all elements from second list until you hit that same duplicate, then write down the duplicate and continue. The part where it's a bit more tricky with $k>2$ is that the duplicate may not be in every list to do the above (and this process cannot be done sequentially, i.e.
l1+l2+l3 is generally not the same as
+ denotes this operation of finding the superset order list).
It should be easy to extend the above to any $k$. Use a hash to find which lists each unique element belongs to. Then traverse along the first list using the above logic - writing down all elements until you hit first duplicate, in which case write down all elements (that haven't been written down yet) in all other lists before that duplicate and keep doing that until you reach the end of first list. If haven't reached the end of second list, continue same algorithm there and so on. Each list will be traversed twice - once to get the duplicates, and second time to do the above, making it $O(n)$. A compatibility error will be discovered if you iterate along a list but can't find the duplicate (because it was already written down in an earlier pass).