Я пытаюсь найти лучший способ решить следующую проблему.Лучше всего я имею в виду менее сложный.
В качестве входных данных используется список кортежей (начало, длина), таких как:
[(0,5),(0,1),(1,9),(5,5),(5,7),(10,1)]
Каждый элемент представляет последовательность своим start * 1007.* и длина , например (5,7) эквивалентна последовательности (5,6,7,8,9,10,11)
- список из 7 элементов, начиная с 5. Можно предположить, что кортежи отсортированы по элементу start
.
Выходные данные должны возвращать неперекрывающуюся комбинацию кортежей, которые представляют самые длинные непрерывные последовательности.Это означает, что решение представляет собой подмножество диапазонов без перекрытий и пропусков и является максимально длинным - хотя их может быть несколько.
Например, для заданного входного значения решение:
[(0,5),(5,7)]
эквивалентно (0,1,2,3,4,5,6,7,8,9,10,11)
. Откат назад - лучший подход для решения этой проблемы?
Меня интересуют любые другие подходы, которые люди могут предложить.
Также, если кто-то знает официальную ссылку на эту проблему или другую похожую, я хотел бы получить ссылки.
Кстати - это не домашняя работа.
Редактировать
Просто, чтобы избежать некоторых ошибок, это еще один пример ожидаемого поведения
для ввода, подобного[(0,1),(1,7),(3,20),(8,5)]
правильный ответ [(3,20)]
эквивалентен (3,4,5, .., 22) длиной 20. Некоторые из полученных ответов дадут [(0,1),(1,7),(8,5)]
эквивалентно (0,1,2, ...), 11,12) как правильный ответ.Но этот последний ответ неверен, потому что он короче [(3,20)]
.