Задача решается алгоритмом из семейства line-sweep.
Наброски решения (только в несколько иной формулировке) -- здесь (секция "Area of the union of rectangles").
Вкратце: она элементарно сводится к поиску множества точек прямоугольника (см. первый пост iv_an_ru), не принадлежащих объединению множества других прямоугольников; левые и правые рёбра этих прямоугольников сортируются по возрастанию, после чего некая воображаемая линия "сканирует" их слева на право, между любыми двумя соседними линиями легко строится множество "свободных" точек, не принадлежащих ни одному прямоугольнику.
Думаю, это оптимальный алгоритм.

miksoftПо возрастанию чего? длины? - так они все одинаковой длины.
А вообще это не алгоритм, а поток сознания.
По возрастанию абсциссы, очевидно (написал я, пожалуй, криво, но если б Вы прошли по указанной ссылке, то сразу поняли бы о чём речь).
Если Вы не знаете такой техники, то лучше отправляйтесь штудировать педивикию хотя бы %) техника в ряде задач очень полезна, например -- в данной.

iv_an_ruАлгоритмы сканирования пикселей оптимальны только для сложных или очень-очень многочисленных фигур и --- сюрприз --- растра. У нас 6 очень простых фигур, и нигде не сказано, что у них координаты одновременно небольшие и целочисленные.
Помилуйте, при чём здесь пиксели? Указанный алгоритм работает с непрерывными координатами.

iv_an_ruМожно, конечно, скрестить ужа с ежом --- сначала модифицировать исходные прямоугольники "голодной козой", а потом именно таким сканированием искать свободное место. Это будет хорошо работать в т.ч. для фигур сложной формы, а не только для параллельных осям "ящиков". Но это точно не быстрее обегания матрицы 11x11.
Вы не поняли алгоритма. Ну неужели так сложно пройти по указанным ссылкам?
Для сложных фигур он вообще работать не будет, равно как и в случае поворота прямоугольников на угол, не кратный pi/2. Это не "сканирование" в обычном смысле, скачки между ближайшими вертикальными линиями (будь то левое или правое ребро какого-либо прямоугольника) происходят "мгновенно", за одну итерацию, что логично -- между ними множество "свободных" точек на вертикальной воображаемой линии остаётся неизменным, потому и никакой растр не нужен.
Сложность алгоритма при правильном выборе структур данных -- O(N*logN).

iv_an_ru, а вам не кажется нелепой ситуация, в которой вы меня уверяете в том, что я имею ввиду именно алгоритм сканирования, хотя я говорю про совершенно другой алгоритм?

iv_an_ruCтранно, ссылку даёте как раз на алгоритм сканирования по возрастающей координате с предварительной сортировкой событий по этой координате, сами пытаетесь высказать то же самое.
Ага-ага. Теперь перечитайте свои пассажи про "произвольные фигуры". Про сортировку каких координат вы там писали? %)))

iv_an_ruЕсли вам кажется, что без "голодной козы" этот метод будет удобен
Не очень понял, чего вы так бегаете с этой козой. Переход от исходных прямоугольников и впихиваемого прямоугольника к новым "обрамлённым" прямоугольникам и впихиваемой точки -- очевиден настолько, что на фоне общего алгоритма совершенно не требует внимания, хотя я всё же указал, что его сделать нужно (см. мой первый же пост в этом топике).

Как видно, задача сводится к поиску ГМТ внутри некоего обрамляющего прямоугольника (в общем случае -- плоскости), не принадлежащих ни одному заданному прямоугольнику (то есть, не принадлежащих их объединению, поиск которого -- классическая задачка для sweep line).

iv_an_ru попробуйте не абстрактную идею высказать, а продемонстрировать код.
Это не "абстрактная идея", а вполне конкретный алгоритм. Достаточно широко известный, чтобы легко гуглиться. Вот, например, одна из первых ссылок в гугле . С той лишь минимальной разницей, что между двумя событиями в данной задаче нас интересует не длина вертикальных отрезков, проходящих через хотя бы один прямоугольник, а множество вертикальных отрезков, не проходящих ни через один прямоугольник, что позволяет использовать точь-в-точь такой же подход.

iv_an_ruНу так заранее огорчу --- там полезут вредные случаи, для которых надо будет городить как раз "память" для данных из уже пройденных координат, именно с указанием точного значения X, когда событие происходило. Или запоминать, какой именно номер прямоугольника связан с каким событием, и лазить в "двумерные" данные по ранее пройденным объектам.
Пф, ну конечно надо "запоминать" ребро какого прямоугольника проходится линией; и более того -- запоминать какое это именно ребро, левое или правое, чтобы знать, включать или исключать из активного множества прямоугольник, и какой именно. А что в этом ужасного? Вас пугает дополнительная память на индекс прямоугольника и флаг левое/правое в структуре события?

rt123, решение O(N^2) было предложено почти сразу, тут больше интересно решить за O(N*logN).