ACL talk:Page/Жадные алгоритмы/Задача о покрытии отрезков точками/Решение Маркеевой Ларисы/c000100

Материал из DISCOPAL
Перейти к: навигация, поиск

Будем считать, что отрезки заданы парами (a,b) - где числа есть соответственно начало и конец отрезка. Пусть дано n отрезков. за O(n*logn) сортируем отрезки сначала по a, затем по b. (будет два массива, отдельно друг от друга.) найдем множество точек I (принадлежность точки множеству I обозначим () = I) s=2 for i = 1 to n, : (если i = 1,b1=I  ; если b(i)>a(s) s++; если b(i)<= a(s) пометить b(s) И i+ = s ; s++ )


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


Сложность алгоритма - сортировка за O(nlogn) + пометка за линейное время = сложность O(nlogn)

[ Хронологический вид ]Ответы

(нет элементов)

Войдите, чтобы комментировать.