Нужна эффективная жадность для покрытия отрезка

Question

Задано n отрезков линии (по оси X) с координатами [li; ри]. Вы должны выбрать минимальное количество сегментов, которые покрывают сегмент [0; M]. Разработать жадный алгоритм для решить эту проблему.

Вот что я сделал: сортируя их по начальным точкам в порядке возрастания, затем я выбираю самую длинную, вторую самую длинную .... Но вот проблема: предположим, мы хотим получить сегмент [0,12], и есть 3 сегмента: [0,5 ], [5,12], [0,10]. Следуйте алгоритму, он займет [0,10], тогда он не охватит весь сегмент, но если мы возьмем другие два, он покроет.

Ребята, у вас есть другая идея? без сортировки и взятия самых длинных строк не получается. мы хотим охватить сегмент [0,12] и есть 5 сегментов: [0,2] [2,10]. [10,12], [0,6] [6,12] Следуйте своему алгоритму, первые три выбраны, но последние 2 оптимальны

Answer 1

Я не думаю, что это должна быть непересекающаяся обложка, или вы можете использовать перекрывающуюся обложку.В вашем примере просто возьмите [0,10], а затем [5,12].Сначала посмотрите на все сегменты, начинающиеся с 0, затем найдите самый длинный.Мы назовем это [0, m], а затем рассмотрим все отрезки [a, b], такие что am, возьмем тот, у которого наибольшее mПродолжайте итеративно таким образом.Для этого потребуется | N | * | C |, где N - количество отрезков линии, а c - количество отрезков, взятых для покрытия линии.

Answer 2

Я предполагаю, что перекрывающиеся интервалы хороши, если они дают оптимальный ответ.

Прежде чем я продолжу, я хотел бы спросить, знаете ли вы, почему ваш жадный подход не дал оптимального ответа? (подумайте минуту, прежде чем читать следующий абзац.)

Если вы не поняли, почему, позвольте мне рассказать вам. Вы всегда выбираете самый длинный интервал (после сортировки), но он может быть не самым длинным интервалом, который покрывает непокрытый сегмент интервала. Допустим, у вас есть 0-10, 5-14, 9-15. Если вы выбираете по наибольшему интервалу, то вы собираетесь выбрать все сегменты. После того, как вы выбрали 1-й сегмент, выбор 2-го охватывает только 4 единицы дополнительно, тогда как выбор 3-го охватывает 5 дополнительных единиц. Таким образом, ясно, что подбор, основанный на длине самого длинного интервала, не дает оптимального решения.

Думаю, теперь вы поняли идею. Учитывая, что это помечено как домашнее задание, неуместно, если я представлю решение за пределами этого пункта.

Answer 3

Ребята, у вас есть другая идея?

Я могу придумать действительно дурацкий алгоритм N ^ N.