# 2D interval scheduling problem

Suppose I give you $$n$$ axis-aligned rectangles with a specified width, height, and x-position (of the left edge) $$\{(w_i, h_i, x_i) \mid i \in \{0, \ldots, n - 1\}\}$$, as well as a bound $$(y_\mathrm{min}, y_\mathrm{max})$$ on the valid y-positions. These rectangles must have integer-valued coordinates for their vertices. Is there an efficient (e.g.: $$O(n^3)$$) approximation algorithm that gives a sequence $$\{y_0, \ldots, y_{n - 1}\}$$ of y-positions such that the number of overlaps between any two rectangles (i.e.: edges in the overlap graph) is minimized (and hopefully zero)?

Note that if $$y_\mathrm{max} = 10$$ and $$h_k = 3$$, then $$y_k = 9$$ would be invalid, since the top edge would be at $$12$$ which is more than $$10$$.

• Just to be sure, if we have $w_i$ and $x_i$ we can safely assume we know for each rectangle its projection into the $x$ axis to be $[x_i, x_i + w_i]$. So we only need to choose for every rectangle the $y_i$ coordinate of its lower edge. Is that correct? Dec 31 '19 at 17:47
• Yes, that is correct. Dec 31 '19 at 18:00
• It reminds me to a very difficult problem which can be seen as a 1D version of this problem. Check it here. This was the hardest problem in the ICPC World Final competition (so you can assume it was very hard). Check the editorial (problem H). Your problem can be reduced to this problem (for the zero overlapping case). They quote this paper “Scheduling Unit-time Tasks With Arbitrary Release Times and Deadlines” by Garey, Johnson, Simons, and Tarjan (SICOMP, 1981). Dec 31 '19 at 18:09
• Ohh, I missed something important from your problem, $[y_{min}, y_{max}]$ is fixed for all rectangles. Disregard previous message, I'll leave it in case the quoted paper helps you somehow, but it is not the same problem. Dec 31 '19 at 18:15
• I think in graph theoretic terms this is a variant of $T$-coloring problem in interval graphs, and maybe related to the frequency assignment problem. Jan 2 '20 at 1:47