Заметание

Рассмотрим следующую задачу.

Закраска прямой. На числовой прямой окрасили N отрезков. Известны координаты левого и правого концов каждого отрезка (Li и Ri). Найти длину окрашенной части числовой прямой.

Ограничения: Li и R i - целые, -1000 ≤ Li ≤ Ri ≤ 1000, 1 ≤ N ≤ 1000, время 1 с.

Ввод из файла INPUT.TXT. В первой строке находится число N, в следующих N строках - пары Li и R i.

Вывод в файл OUTPUT.TXT. Вывести одно число – длину окрашенной части прямой.

Примеры

Ввод 1 Ввод 2

2 1

1 3 10 10

2 4

Вывод 1 Вывод 2

3 0

Отсортируем концы отрезков по возрастанию. Будем просматривать отсортированный массив слева направо, прибавляя к счетчику 1 в случае начала отрезка, и вычитая 1 для конца отрезка. Если счетчик получает значение 1 в начале очередного отрезка, запомним соответствующее значение координаты L. Если счетчик становится равным 0 в некотором конце отрезка с координатой R, то очередное объединение отрезков закончилось, и точки до следующего начала отрезка не принадлежат ни одному отрезку. Прибавляем величину R-L к общей длине окрашенной части.

Приведем текст программы для решения этой задачи.

Program PaintX;

Const

Max=2000;

Type

Segm=record

X: integer; {координата}

Vid: integer; {1-левый конец, -1-правый}

end;

Var

M, N, i, j, K, L: integer;

Lp: longint; {общая длина окрашенной части прямой}

S: array [1..Max] of Segm;

Fin, Fout: text;

Procedure Sort; {сортировка на месте}

Var

i, j: integer;

B: Segm;

Begin

For i: =2 to K do

For j: =K downto i do { пузырек }

if (S[j].X< S[j-1].X) then

begin

B: =S[j];

S[j]: =S[j-1];

S[j-1]: =B;

end;

End;

Begin

Assign(Fin, 'input.txt');

Reset(Fin);

ReadLn(Fin, N);

K: =0; {число концов}

For i: =1 to N do

begin

K: =K+2;

ReadLn(Fin, S[K-1].X, S[K].X);

S[K-1].Vid: =1; {признак левого конца}

S[K].Vid: =-1; {признак правого конца}

end;

Close(Fin);

Sort;

Lp: =0; {общая длина окрашенной части прямой}

M: =0; {количество отрезков, содержащих текущую координату}

For i: =1 to K do

begin

M: =M+S[i].Vid;

if (M = 1) and (S[i].Vid = 1) then L: =S[i].X;

if (M = 0) and (S[i].Vid = -1) then Lp: =Lp+S[i].X-L;

end;

Assign(Fout, 'output.txt');

Rewrite(Fout);

Write(Fout, Lp);

Close(Fout);

End.

При увеличении размерности необходимо использовать один из вариантов быстрой сортировки.

В рассмотренной задаче мы продвигаемся по числовой прямой, обрабатывая два вида событий: начало и конец какого-либо отрезка. Между точками событий принципиально ничего не изменяется.

Подобный подход называют методом заметания (выметания, скользящей прямой, sweeping). Обычно он включает в себя следующие этапы:

· выделение точек событий;

· сортировка точек событий;

· последовательное продвижение по точкам событий с обработкой точек в зависимости от вида событий.

В нашей задаче всего два вида событий, но их может быть и больше.