My first post here so please correct me if my terms are off or needs clarification.
Suppose I have several sets of lists of spans. I define a span as a pair of indexes: begin and end index in a string. You can also think of a span as a consecutive sequence of 1's in a bitarray. e.g. 00111 is a span of (2,5).
I will have up to 10 sets of lists of spans. Each set will have on the order of 30 spans in each list. In case it's important, a span can have no more than 20 bits but spans will likely be small, spanning on average 5 bits.
I have to pick one (or none) span from each set such that there are no overlapping bits among them.
Let's suppose 2 sets of lists of spans for a moment.
The first set has the following list of spans:
- (0,5) or 11111
- (0,3) or 11100
- (1,4) or 01110
The second set has the following list of spans:
- (2,4) or 00110
- (3,5) or 00011
- (4,5) or 00001
The valid combinations are [(0,3),(3,5)], [(0,3),(4,5)], and [(1,4),(4,5)].
I could try all combinations, but with 10 sets of 30 spans, that's 30^10 combinations!
Is there some bit manipulation magic I could use? Or could I sort the spans and eliminate many of the combos? e.g. when considering (0,3), I can sort the next list of spans by the beginIndex and rule out everything that starts with 2 or less.
This is similar to this problem: Finding a pair of non-overlapping bit vectors But in mine, the bits are consecutive so there must be a way to take advantage of the beginning and ending boundaries