Given a list of lists of positive integers, output a subset of them so their union forms a continuous non-empty range with no numbers missing. For example, consider this input:
[
[1, 2, 3, 5],
[2, 4, 6],
[7, 9, 11]
]
The union of the first 2 forms a continuous sequence: [1, 2, 3, 4, 5, 6]
with no numbers missing. Adding the last one would create [1, 2, 3, 4, 5, 6, 7, 9, 11]
which is missing 8
and 10
so would not be a valid answer.
Output can be either the indexes of the included lists or the lists themselves.
Lists are guaranteed to be sorted, and the list of lists will also be sorted lexicography. All lists will have at least one element. There may be more than one valid solution, if so you may choose output any of them, or all of them, or some of them. If you output multiple solutions all must be valid and they must be clearly separated.
There will never be no solutions.
Test cases
Input | Output |
---|---|
[[1, 2, 3]] |
0 |
[[1, 3], [2, 4]] |
0, 1 |
[[2, 4], [4, 23], [8, 10], [8, 12], [9, 13], [10, 23], [11, 14]] |
2, 3, 4, 6 |
[[1, 3], [2, 4], [5,7], [6,8]] |
0,1 OR 2,3 OR 0,1,2,3 |
[[1, 17], [2,23], [3,42], [4,17], [5, 3912], [6]] |
5 |
[[1,5][5,6][5,6,7]]
, could just be2
? \$\endgroup\$