У меня есть набор прямоугольников, и я пытаюсь найти все прямоугольники, которые могут полностью поместиться в какой-то другой прямоугольник.
Я могу разместить все эти прямоугольники на плоскости так, чтобы левый нижний угол каждого прямоугольника будет в координатах 0,0. Верхние края этих прямоугольников создадут нисходящие ступени, и я легко могу определить, какие прямоугольники не являются частью этих ступеней, поэтому я знаю, что они могут полностью вписаться в какой-то другой прямоугольник.
Проблема в том, что когда я попробуйте добавить новый прямоугольник в плоскость, которая больше, чем все остальные прямоугольники, мне нужно проверить каждую лестницу и «снять отметку» с нее, потому что она больше не является частью лестницы. У меня было «m» старых прямоугольников и я хочу добавить «n» новых прямоугольников, что потребовало бы m * n сравнений.
Возможно ли сделать это в n * log m? Спасибо