Daily bit(e) of C++ | Smallest interval covering k sorted sequences.
Daily bit(e) of C++ #147, Common interview problem: Smallest interval covering k sorted sequences.
Today we will look at a common interview problem: Smallest interval covering k sorted sequences.
Given k sequences of sorted integers, determine the smallest closed interval that covers at least one element from each sequence. For intervals of the same size should be ordered based on their lower bound value (i.e. [0,2]<[1,3]).
For example, for the sequences {1,2,3}, {4,5,6,7}, {8,9}, the best we can do is {3,8} since the sequences do not overlap.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/cqKo5WeMY.
Solution
Since we have to come up with an interval that covers an element from each sequence, let’s start with an arbitrary group of elements, one from each sequence. They naturally form the interval [min(elements), max(elements)].
Is there an operation that can potentially improve this interval? If we limit ourselves to processing elements in their sorted order, the only operation that can potentially improve this interval is swapping the current lower bound for the next element in that sequence. Swapping any other element will not improve the lower bound and can only worsen the upper bound.
We can therefore start with the first element from each sequence, which will give us the initial interval and then repeatedly swap out the lower bound until we run out of elements.
To keep track of the current interval, we can use an indirect multiset, which will allow us to remove and add an element in O(log(k)), and since we will repeat this operation n times (where n is the total number of elements), we end up with O(n*log(k)) time complexity and O(k) space complexity.
