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}$
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityGiven 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}$
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.