有n个矩形，每个矩形可以用a,b来描述，表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d（相当于旋转90度）。

这是一个经典的矩形嵌套问题，可以通过贪心算法来解决。具体步骤如下：

1. 将所有矩形按照长或宽的大小排序，即将所有矩形按照max(a,b)从小到大排序。

2. 从小到大遍历每个矩形X，尝试将其嵌套在已有的矩形Y中。

3. 对于每个矩形X，从已有的矩形中选择一个可以嵌套的矩形Y，并且使嵌套后的面积最大。

4. 如果找不到可以嵌套的矩形Y，就将X作为一个新的矩形加入到已有的矩形中。

5. 重复步骤2-4，直到所有矩形都被处理完毕。

6. 最终已有的矩形就是最大的矩形集合。

这个算法的时间复杂度是O(nlogn)，其中n是矩形的个数。

相关问题

有n个矩形，每个矩形可以用a,b来描述，表示长和宽。矩形x(a,b)可以嵌套在矩形y(c,d)中当且仅当a<c,b<d或者b<c,a<d（相当于旋转90度）。例如（1,5）可以嵌套在（6,2）内，但不

可以嵌套在（3,4）内。现在给定n个矩形，请你找出其中最多可以嵌套多少个矩形。

解题思路：

1. 首先将所有矩形按照长和宽从小到大排序，这样可以保证后面的矩形可以嵌套在前面的矩形中。

2. 定义一个数组dp，dp[i]表示以第i个矩形为最外层矩形时，最多可以嵌套多少个矩形。

3. 对于每个矩形i，枚举前面的所有矩形j，如果矩形i可以嵌套在矩形j中，则更新dp[i]为dp[j]+1。

4. 最终答案为dp数组中的最大值。

代码实现：

有n个矩形,每个矩形可以用a,b来描述,表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d(相当于旋转90度)。例如(1,5)可以嵌套在(6,2)内,但不能嵌套在(3,4)中。请设计一个动态规划

题解：

首先我们可以将每个矩形的长和宽进行排序，使得每个矩形的长大于等于宽。然后我们可以将所有矩形按照长从小到大排序，如果长相同则按照宽从小到大排序。这样可以保证后面的矩形不会嵌套到前面的矩形中去。

设 $dp[i]$ 表示以第 $i$ 个矩形为最大矩形的最大嵌套深度。

对于第 $i$ 个矩形，它可以嵌套在前面的任意一个比它长宽都大的矩形中，所以可以得到状态转移方程：

$$ dp[i] = \max\limits_{j<i}(dp[j]+1) $$

其中 $j$ 表示比第 $i$ 个矩形长宽都大的前面的矩形。

最终答案即为 $dp$ 数组中的最大值。

时间复杂度为 $O(n^2)$，可以通过本题。

代码实现：