Я думаю, что вы можете атаковать это с помощью довольно типичного подхода линии сканирования.
Сначала рассмотрите горизонтальную линию сканирования, проходящую от вершины рисунка к основанию.Обратите внимание, что ширина, пересекаемая линией сканирования, может изменяться только при прохождении через конечную точку вертикального сегмента.
Так что для горизонтальной линии сканирования вы можете игнорировать горизонтальные сегменты.Возьмите все конечные точки вертикальных сегментов и отсортируйте их по их вертикальному расположению.(Каждая конечная точка знает, является ли она «верхней» конечной точкой или «нижней» конечной точкой своего сегмента).
Обрабатывает этот отсортированный список для имитации линии сканирования.Поддерживать «активный набор» S, инициализированный как пустой.Когда вы достигнете «верхней» конечной точки, добавьте ее сегмент к S. Когда вы дойдете до «нижней» конечной точки, удалите ее сегмент из S. Убедитесь, что ширина активного набора всегда соответствует вашему ограничению, и все готово.
Используйте сбалансированное двоичное дерево (например, C ++ std::set) для представления активного набора, используя горизонтальную позицию для функции сравнения.Это позволяет O (1) извлечь самый левый и самый правый сегмент в наборе, поэтому вычисление ширины O (1).Он также позволяет вставлять и удалять O (log n), а поскольку вы вставляете и удаляете каждый вертикальный сегмент ровно один раз, весь цикл занимает O (n log n).
Повторите симметрично для вертикальной линии сканирования.
Каждая сортировка - O (n log n), каждое сканирование - O (n log n), умноженное на два для каждой ориентации ... Таким образом, общий алгоритм - O (n log n).