Видеозаписи лекций ЛКШ

Другие задачи: точка, покрытая максимальным количеством отрезков; объединение отрезков; длина объединения.

Лектор: Пётр Калинин

2013.Июль Параллель B'

Отрезки на прямой

Алгоритм покрытия отрезка отрезками. Метод сканирующей прямой. Сжатие координат. Сортировка событий.
Реализация алгоритма покрытия отрезка отрезками
Другие задачи: точка, покрытая максимальным количеством отрезков; объединение отрезков; длина объединения.
Разбор задачи A ("Пересадки") из контеста третьего дня: пересечение двух отрезков на прямой. Пересечение прямоугольников.
Разбор задачи B ("Объединение отрезков") из контеста третьего дня.
Разбор задачи С ("Дорешивание") из контеста третьего дня.
Разбор задачи D ("Минимальное покрытие") из контеста третьего дня: жадный алгоритм и доказательство его оптимальности.
Разбор задачи E ("Китайские часы") из контеста третьего дня.