Efficient Frame-Cutting Algorithm

Question

Came across problem that initially seemed pretty simple; however, I couldn't find an efficient solution. Can you guys help?

---

A sheet is comprised of rectangles (frames) of various lengths and widths that may have gaps but do not intersect. Find the least amount of straight cuts (vertical or horizontal) that separate those rectangles. Cuts have to be made through the entire available board.

Input consists of the number of rectangles followed by top-left and bottom right coordinates of each one. Output should have the number of cuts followed by 2 points representing vertical/horizontal cut or NA if there was no solution. Note that several optimal solutions are possible.

Input:

(3,3)

(0,0) (1,1)

(2,0) (3,1)

(0,2) (3,3)

Output:

2

(0,2) (2,2)

(1,0) (1,2)

Input:

(5,5)

(0,0) (3,1)

(4,0) (5,3)

(0,2) (1,5)

(2,4) (5,5)

Output:

NA

Answer 1

It is a classic example of Cutting Stock problem solved by P. Y. Wang's bottom-up two-dimensional algorithm (as one possible approach).

Google search links usually lead to paid-access articles, but some publically available descriptions can be found as well (PDF version, p.6)