Решает ли жадное удаление интервалов с большинством конфликтов планирование интервалов?

Мы можем решить проблему планирования, в которой мы должны выбрать самый большой набор непрерывных интервалов, которые не пересекаются, с помощью жадного алгоритма: мы просто продолжаем выбирать интервалы, которые заканчиваются раньше всего: http://en.wikipedia.org/wiki/Interval_scheduling

Судя по всему, жадный подбор интервалов с наименьшим количеством конфликтов не работает.

Мне было интересно, работает ли объединение всех интервалов в один большой набор, а затем жадное удаление интервала с наибольшим количеством оставшихся конфликтов (пока в интервалах не будет конфликтов). Я могу представить себе реализацию этого жадного алгоритма с очередью приоритетов: каждый раз, когда мы удаляем интервал X с наибольшими конфликтами из очереди приоритетов, мы обновляем другие интервалы, которые раньше конфликтовали с интервалом X, так что теперь другие интервалы помечаются как имеющие 1 меньше конфликтов.

Это работает? Я пытаюсь придумать контрпример, чтобы опровергнуть это, и не могу.


algorithm
person dangerChihuahua007    schedule 05.04.2014    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Вот контрпример. Идея состоит в том, чтобы сбросить требуемый интервал с самого первого выбора. Количество конфликтов справа.

        ====    2
       ----     3
      ----      3
    ====        4
  ----          3
 ----           3
====            2

Очевидно, мы захотим выбрать три полужирных (====) интервала и отбросить четыре тонких (----) интервала. Другого способа получить три непересекающихся интервала нет.

Кстати, вы можете найти учебник по TopCoder по жадным проблемам, интересным, поскольку он начинается с обсуждения нескольких подходов к одной и той же проблеме.

person Gassa    schedule 05.04.2014