Входные данные представляют собой набор из n (n> 10000) прямоугольников. На выходе должно быть минимальное количество независимых (непересекающихся) наборов прямоугольников. Таким образом, минимально возможное количество наборов, где каждый набор имеет группу непересекающихся прямоугольников.
Поскольку входные данные очень велики, то какой алгоритм является наиболее эффективным для решения этого типа проблемы. Например: прикрепленная фотография хорошо описывает мою проблему с верхней частью как входом и нижней частью как выходом
Редактировать: Да, 1 можно считать минимальным числом, еслии только если этот единственный выходной набор не будет содержать никаких пересекающихся прямоугольников.
Я попытался с помощью грубой силы выбрать каждый прямоугольник и перебрать все остальные. Это на самом деле работало, но, к сожалению, сложность времени ужасна для большого ввода и может длиться более пяти минут!
Я искал проблему и нашел алгоритм (от Chalermsook и названный MISR), но я не сталЧтобы понять его подход или более четко, мне нужен пример, использующий этот подход для лучшего объяснения.