Я пытаюсь найти лучший способ решить следующую проблему. Лучше всего я подразумеваю менее сложный.
В качестве ввода введите список кортежей (начало, длина), например:
[(0,5),(0,1),(1,9),(5,5),(5,7),(10,1)]
Каждый элемент представляет последовательность по началу и по длине, например (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)
это откат наилучшего подхода для решения этой проблемы?
Меня интересуют различные подходы, которые могут предложить люди.
Кроме того, если кто-то знает формальную ссылку на эту проблему или другую, похожую, я бы хотел получить ссылки.
Кстати - это не домашнее задание.
Edit
Чтобы избежать некоторых ошибок, это еще один пример ожидаемого поведения
для ввода типа [(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)]
.