Задачи про отрезки: какой приём когда
Сводка по разделу и по соседним: у задач про отрезки четыре разных техники, и выбор определяется формулировкой.
3 мин
Задач вида «даны отрезки, найдите…» очень много, а техник — четыре. Эта статья о том, как по условию понять, какая нужна.
Четыре техники
| техника | суть | где описана |
|---|---|---|
| сортировка по правому концу | жадный выбор | жадность на отрезках |
| сортировка по левому концу | слияние на лету | жадность на отрезках |
| события и баланс | проход по точкам | эта статья и соседние |
| куча активных | динамический выбор | жадность с кучей |
По формулировке
| в условии | техника |
|---|---|
| максимум непересекающихся | правый конец, жадно |
| минимум точек, чтобы проколоть все | правый конец, жадно |
| покрыть отрезок отрезками | левый конец, тянемся дальше |
| объединить, найти длину покрытия | левый конец или события |
| самая покрытая точка | баланс |
| сколько отрезков покрывает точку (запросы) | запросы как события |
| удалить вложенные | левый конец, максимум правых |
| пересечение всех | максимум левых против минимума правых |
| сколько аудиторий нужно | баланс или куча |
| дуги на окружности | разрез или удвоение |
| прямоугольники на плоскости | сжатие координат |
Как выбирать
Три вопроса, которые обычно решают дело.
Нужен ли выбор подмножества отрезков? Если да — это жадность, и главное подобрать ключ сортировки. Если нет, а нужна агрегированная характеристика (длина, максимум покрытия, число кусков) — это события.
Нужно ли отвечать в конкретных точках? Если да — события с третьим типом, офлайн.
Меняется ли набор отрезков по ходу? Если да, ни то, ни другое не подходит: нужна структура данных — дерево Фенвика по сжатым координатам или дерево отрезков.
Что проверять в любой такой задаче
Ошибки в задачах про отрезки почти всегда одинаковые. Список стоит держать перед глазами:
- тип границ — замкнутый отрезок, полуинтервал или клетки; от этого зависит порядок событий;
- касание концами — считается ли пересечением;
- вырожденные отрезки ;
- совпадающие отрезки;
- один отрезок во входных данных;
- ноль отрезков — не всегда исключено условием;
- переполнение — координаты до , произведения и суммы длин уже за пределами
int.
Первые два пункта дают больше всего неверных ответов, потому что на случайных тестах почти не встречаются. Их стоит проверить руками до отправки.
Стресс
Все задачи этого раздела прекрасно стрессуются: эталон пишется в лоб перебором координат.
// эталон: покрытие в каждой целой точке маленького диапазона
for (int x = -50; x <= 50; x++) {
int c = 0;
for (auto& [l, r] : seg) if (l <= x && x <= r) c++;
best = max(best, c);
}
Генерируйте отрезки с координатами в диапазоне от до : именно там плотно встречаются касания, совпадения и вложенности, на которых решения и ломаются. Все алгоритмы этого раздела проверены ровно так.