💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

Заметание

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

Закраска прямой. На числовой прямой окрасили 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). Обычно он включает в себя следующие этапы:

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

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

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

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