Given a collection of sets $C= \{S_1,S_2,\cdots,S_n\}$ such that each set $S_i \in C$ is sorted and has at least $k$ elements.
What is the most efficient algorithm for finding the intersection of these sets: $\bigcap_{S_i \in C}{S_i}$
$\begingroup$
$\endgroup$
-
$\begingroup$ @Raphael I tried having a universal set that contains all elements in the sets, then iterate these elements and check their existence in $S_i$. I am looking for a better algorithm. $\endgroup$ – M.M Jun 15 '15 at 12:19
-
$\begingroup$ Related question. $\endgroup$ – Raphael♦ Jun 15 '15 at 12:55
$\begingroup$
$\endgroup$
If the least elements in all $S_i$ are equal then pick it for final set else pick least element among all $S_i$ and remove (remove minimum among all sets and not minimums of all sets). This works in $O(n*|C|*log |C|)$, where $|C|$ is the total number of elements in $C$ (not it's cardinality). This works since all your $Si$ are sorted and removal of element will maintain the sorted order.
