Исходные данные:
0. Считаем, что грани всех прямоугольников параллельны осям.
1. Дано множество P N-мерных прямогуольников , |P|=K
2. Дан охватываювающий N-мерный прямоугольник R.

Требуется:
1. Получить минимальное по мощности множество Q непересекающихся N-мерных прямоугольников,
|Q|=M (неизвестна), таких что sum(P)+sum(Q) = R (объединение равно охватывающему),
sum(P)*sum(Q) = 0 (пересечение их пусто). (sum(P) - объединение входящих в P прямоугольников).

Алгоритм полного перебора:
1. Из каждой вершины элемента множества P, а также из точек пересечения ребер с гранями проводим отрезки во все вершины R. Получаем E*K*(2 ^N ) ² =K*2 ^2*N отрезков. (E - некоторая константа)

2. Отбрасываем отрезки, пересекающие хотя бы один элемент из P, получаем L=K/C*2 ^2*N отрезков, где C - некоторая константа. Каждый такой отрезок является теперь диагональю одного из возможных и допустимых прямоугольников множества Q. Обозначим это множество как T. Условие sum(P)*sum(T)=0 выполняется.

3. Перебором всех подможеств множества T, начиная с одноэлементного, находим Q.

Оценка вычислительной сложности:
O( 2 ^L ) , т.е. в худшем случае O(2 ^E*K*22*N )

P.S. Очевидно, этот алгоритм можно улучшить, но сложно придумать более тупой и медленный

Пример для двухмерного случая.