最大的矩形子集，使得没有矩形适合任何其他矩形

Question

给定N个矩形的高度和宽度。任务是找到最大子集的大小，使得没有一对矩形可以彼此匹配。请注意，如果 H1 ≤ H2 且 W1 ≤ W2，则矩形 1 适合矩形 2。

Input: arr[] = {{1, 3}, {2, 2}, {1, 3}}
Output: 2
The required sub-set is {{1, 3}, {2, 2}}
{1, 3} is included only once as it can fit in {1, 3}

Input: arr[] = {{1, 5}, {2, 4}, {1, 1}, {3, 3}}
Output: 3

谁能解释一下这个问题背后的动态规划直觉？

Answer 1

是的。让我们按高度升序对输入进行排序，并考虑我们选择任何一个矩形的场景。

(1) 我们现在不能选择任何第二个具有相同宽度或高度的矩形，因为 non-equal 尺寸较小的矩形可以包含在较大尺寸（例如 2×6可以包含在2×8中，或者2x4可以包含在2×6中)

(2) 我们现在不能选择具有更高高度和更高宽度的任何第二个矩形，因为它显然可以包含第一个矩形。

由于我们已经按高度升序对矩形进行了排序，因此我们必须选择第二个高度更大宽度更小的矩形，这导致以下算法：

Order by height ascending.

Find the longest sequence of strictly
ascending height and strictly decreasing
width.

最大的矩形子集，使得没有矩形适合任何其他矩形

Largest subset of rectangles such that no rectangle fits in any other rectangle

algorithm

dynamic-programming