NEW ANSWER: the following simple algorithm is asymptotically optimal:
Stretch each of the rectangles $C_i$ arbitrarily, to the maximal extent possible such that the rectangles remain pairwise-disjoint.
The number of holes is at most $k-2$. This is asymptotically optimal, as there are configurations in which the number of holes is at least $k-O(\sqrt k)$.
The proofs are in this paper.
The following algorithm, while not optimal, is apparently sufficient for finding a rectangle-preserving partition with $N=O(n)$ parts.
The algorithm works with a rectilinear polygon $P$, which is initialized to the rectangle $C$.
Phase 1: Pick a rectangle $C_i$ which is adjacent to a western boundary of $P$ (i.e, there is no other rectangle $C_j$ between the western side of $C_i$ and a western boundary of $P$). Place $C_i$ within $P$ and stretch it until it touches the western boundary of $P$. Let $E_i$ (for $i=1,\dots,n$) be the stretched version of $C_i$. Let $P=P\setminus E_i$. Repeate Phase 1 $n$ times until all $n$ original rectangles are placed and stretched. In the image below, a possible order of placing the rectangles is $C_1,C_2,C_4,C_3$:
Now, $P$ is a rectilinear polygon (possibly disconnected), like this:
I claim that the number of concave vertices in $P$ is at most $2n$. This is because, whenever a stretched rectangle is removed from $P$, there are 3 possibilities:
- 2 new concave vertices are added (like when placing $C_1,C_4$);
- 3 new concave vertices are added and 1 is removed (like with $C_3$);
- 4 new concave vertices are added and 2 are removed (like with $C_2$).
Phase 2: Partition $P$ into axis-parallel rectangles using an existing algorithm (see Keil 2000, pages 10-13 and Eppstein 2009, pages 3-5 for a review).
Keil cites a theorem that says that the number of rectangles in a minimal partition is bounded by 1 + the number of concave vertices. Hence, in our case the number is at most $2n+1$, and the total number of rectangles in the partition is $N\leq 3n+1$.
This algorithm is not optimal. E.g, in the above example it gives $N=13$ while the optimal solution has $N=5$. So two questions remain:
A. Is this algorithm correct?
B. Is there a polynomial-time algorithm for finding the optimal $N$, or at least a better approximation?