Добавлен Msey,
опубликован
Даны 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;
}
`
ОЖИДАНИЕ РЕКЛАМЫ...
Комментарии пока отсутcтвуют.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.