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

Будем считать, что отрезки заданы парами (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)
{{wl-comment:  }}