Альтернативная жадная стратегия поиска точек в интервалах: работает ли этот подход?

Question

Я пытаюсь решить следующую проблему:

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

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

Однако мне также пришло в голову, что его можно решить, выбрав точку, которая устраняет больше интервалов одновременно. Я знаю, что эта идея не верна, но я не могу найти какой-либо контрпример. Может ли кто-нибудь помочь мне найти контрпример к этой стратегии?

Answer 1

Контрпример:

[-----]         [-----]
[------------]
        [-------------]
[------------]
        [-------------]

Answer 2

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

Возьмите интервалы:

[1, 4], [2, 5], [3, 6], [4, 7], [5, 8], [5, 9], [5, 10], [8, 12]

Жадность поставит точку в 5, так как она имеет наибольшее количество интервалов ( все они, кроме двух) Затем он поместит точку где-то в интервале [1, 4], а другую - в интервале [8, 12].

Ответ Жадности - 3. Но оптимальный способ - поставить одну точку в 4 и одна точка в 8, и все они будут покрыты.

Редактировать: нарисуйте интервалы на бумаге для лучшего понимания.