Кодинг
★ Рубрика: Кодинг
★ Тема: Алгоритмы

Подмножество не пересекающихся отрезков

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

Решение задачи. У каждого отрезка i есть левый конец L[i] и правый конец R[i]. Отсортируем отрезки в порядке возрастания R[i]. В таком порядке будем перебирать отрезки. Очередной отрезок будем добавлять в ответ, если его левая граница больше максимума правых границ уже добавленных отрезков.

Замечание. Это пример задачи на тему "жадные алгоритмы".
 Похожие публикации: Алгоритмы

Войдите, чтобы добавить Ваш ответ. [ Регистрация | Вход ]