MAXimal | |
добавлено: 11 Jun 2008 10:09 Содержание [скрыть] Длина объединения отрезков на прямой за O (N log N)Даны N отрезков на прямой, т.е. каждый отрезок задаётся парой координат (X1, X2). Рассмотрим объединение этих отрезков и найдём его длину. Алгоритм был предложен Кли (Klee) в 1977 году. Алгоритм работает за O (N log N). Было доказано, что этот алгоритм является быстрейшим (асимптотически). ОписаниеПоложим все координаты концов отрезков в массив X и отсортируем его по значению координаты. Дополнительное условие при сортировке - при равенстве координат первыми должны идти левые концы. Кроме того, для каждого элемента массива будем хранить, относится он к левому или к правому концу отрезка. Теперь пройдёмся по всему массиву, имея счётчик C перекрывающихся отрезков. Если C отлично от нуля, то к результату добавляем разницу Xi - Xi-1. Если текущий элемент относится к левому концу, то увеличиваем счётчик C, иначе уменьшаем его. Реализацияunsigned segments_union_measure (const vector <pair <int,int> > & a) { unsigned n = a.size(); vector <pair <int,bool> > x (n*2); for (unsigned i=0; i<n; i++) { x[i*2] = make_pair (a[i].first, false); x[i*2+1] = make_pair (a[i].second, true); } sort (x.begin(), x.end()); unsigned result = 0; unsigned c = 0; for (unsigned i=0; i<n*2; i++) { if (c && i) result += unsigned (x[i].first - x[i-1].first); if (x[i].second) ++c; else --c; } return result; }
|