Добрый день. На первом курсе бакалавриата Академического университета читается годовой курс алгоритмов. Каждая лекция сопровождается семинаром, на котором мы разбираем алгоритмические задачи. Практические семинары проходят в небольших группах. В этом семестре я читаю лекции и веду практику у одной из групп.

Сегодня хочу поделиться с Вами двумя задачами с этих семинаров.

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

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