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)