Сегодня разбираем один из важнейших алгоритмических приёмов — метод сканирующей прямой (или просто scanline).
Этот подход довольно часто встречается в задачах на геометрию, интервалы, события и т. д.
На олимпиаде ШВБ по информатике одна задачек решалась именно этим алгосом, так что смотрим и запоминаем!!😎
Определение & Идея
Вместо того чтобы проверять каждую точку или отрезок по отдельности, мы сортируем все интересные события (начала, концы отрезков, запросы и т.д.) и проходим по ним слева направо, поддерживая нужные параметры.
Изменения происходят только в "интересных точках" — началах и концах отрезков.
Разберем парочку известных задачек
Задача 1
Дано n отрезков [l_i, r_i]. Найти точку, покрытую максимальным числом отрезков.
Идея
Каждое начало отрезка — событие +1, конец — -1.
Сортируем события по координате (при равенстве сначала начала).
Идём слева направо, поддерживая cnt — текущее число активных отрезков.
И получаем максимум cnt — это наш ответ.
struct event { int x, type; };
int scanline(vector<pair<int, int>> segments) {
vector<event> events;
for (auto [l, r] : segments) {
events.push_back({l, 1});
events.push_back({r, -1});
}
sort(events.begin(), events.end(), [](event a, event b) {
return (a.x < b.x || (a.x == b.x && a.type > b.type));
});
int cnt = 0, res = 0;
for (auto e : events) {
cnt += e.type;
res = max(res, cnt);
}
return res;
}По сложности вышло O(n log n). Как вы видите, алгос не супер сложный
Задача 2
Найти суммарную длину объединения всех [l_i, r_i]
Идея
Как и раньше, отсортируем события и пойдём слева направо:
Если cnt > 0, добавляем к ответу длину между текущей и предыдущей координатой;
При входе в отрезок cnt++, при выходе — cnt--.
Работает за O(n log n)
int cnt = 0, res = 0, prev = -inf;
for (auto e : events) {
if (prev != -inf && cnt > 0)
res += e.x - prev;
cnt += e.type;
prev = e.x;
}
Итоги
Как вы видите, сканлайн это:
Довольно универсальный алгос для решения задачек
Объединяет подходы из ДП, геомы и др.
Практика (LeetCode)
Count Days Without Meetings
Maximum Beauty of an Array After Applying Operation
Shifting Letters II
Two Best Non-Overlapping Events
Merge Intervals (обязательно прорешайте эту задачку!!! похожая формулировка была на отборе ШВБ + иногда дают на алгособесе в Яндекс)
Interval List Intersections
Ещё больше разборов и подборок задач на нашей 3х месячной олимпиадной смене по информатике
@postupashki_prog