Алгоритмы: Длина объединения отрезков на прямой | C++

Даны 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;
}


Views: 96

Комментарии пока отсутcтвуют.