Проверка возможности установки крышки
У меня есть набор массивов:
[1,2,3]
[1,2]
[1]
Мне нужно выяснить, существует ли "покрывающий набор" уникальных значений, каждое из которых соответствует значению в массиве. В этом случае набор покрытия может быть [3,2,1], Мне на самом деле не нужен набор, мне просто нужно знать, возможно ли это или нет.
Например, в этом случае это невозможно:
[1,2]
[1,2]
[1,2]
ВОПРОС: Какой самый быстрый способ определить, есть ли решение (не обязательно, что это решение)?
Дополнительная информация:
Я работаю в node и у меня есть более 100 000 таких наборов, которые мне нужно протестировать, и я надеялся на решение O(n), но, похоже, это невозможно.
Я попытался оптимизировать, проверив, что у объединения массивов есть длина>= количество массивов в наборе и обрезка массивов, которые имеют длину>= количество массивов в наборе. Но прав ли я, что тогда это всего лишь грубые попытки найти решение?
PS У меня нет математического фона, чтобы по-настоящему понять проблему покрытия множества, но я считаю, что она связана, следовательно, с ссылками на нее.