问题陈述
Ayimok 是一名巫师。
他的日常任务是将魔法方块排成一行,然后施展魔法咒语。
魔法方块及其排列遵循以下规则:
每个魔法图块的形状都是梯形,高度为 1。
一些魔法图块可能会与其他魔法图块重叠。
魔法方块排列在 2D 坐标系上。
魔法方块的上边缘位于水平线上,其 y 坐标为 1。
魔法方块的下边缘位于水平线上,其 y 坐标为 0。
他必须在施展完魔法咒语后将这些魔法瓷砖移走。 有一天,他发现移除一些魔法瓷砖是如此烦人,因此他决定简化其过程。
现在,他已经学会了“磁化法术”,可以有效地去除魔法瓷砖。 该法术会立即移除一组魔法瓷砖。该组中的任意两块魔法图块必须彼此重叠。
例如,在图1中,他可以对所有三个魔法方块施展磁化法术,将它们一次性移除,因为它们都相互重叠。 (请注意,为了更容易理解,故意更改了魔法图块的高度。)
然而,在图2中,他不能同时对所有三个魔法图块施放磁化法术,因为图块1和图块3不重叠。
他想用最少数量的磁化法术移除所有魔法方块,因为施展该法术需要消耗大量的魔力。
让我们考虑图 3 的情况。他可以通过施放磁化法术三次来消除所有魔法方块;第一个咒语用于图块 1 和 2,第二个咒语用于图块 3 和 4,第三个咒语用于图块 5 和 6。
实际上,他只需施放两次磁化法术就可以消除所有的魔法方块;第一个咒语用于图块 1、2 和 3,第二个咒语用于图块 4、5 和 6。 这是消除所有魔法方块所需的最少法术数量。
给定一组魔法方块,你的任务是创建一个程序,输出最少数量的施放磁化法术,以消除所有这些魔法方块。
可能有一块魔法图块不与其他图块重叠,但是,他仍然需要施展磁化法术来将其移除。
输入
输入遵循以下格式:
N
xLower_{11} xLower_{12} xUpper_{11} xUpper_{12}
xLower_{21} xLower_{22} xUpper_{21} xUpper_{22}
xLower_{31} xLower_{32} xUpper_{31} xUpper_{32}
:
:
xLower_{N1} xLower_{N2} xUpper_{N1} xUpper_{N2}
第一行包含一个整数 N,表示魔法图块的数量。
然后, N 行包含魔法图块的信息。
的 树的 (i+1)第行包含四个整数 xLower_{i1}, xLower_{i2}, xUpper_{i1},和 xUpper_{i2},这意味着 i第一个魔法图块的角点位于 (xLower_{i1}, 0), (xLower_{i2}, 0), (xUpper_{i1}, 1), (xUpper_{i2}, 1).
你可以假设没有两个魔法图块会共享它们的角点。 也就是说,所有 xLower_{ij} 是不同的,并且所有 xUpper_{ij} 也不同。 输入遵循以下约束:
1 \leq N \leq 10^5
1 \leq xLower_{i1} < xLower_{i2} \leq 10^9
1 \leq xUpper_{i1} < xUpper_{i2} \leq 10^9
全部 xLower_{ij} 是不同的。
全部 xUpper_{ij} 是不同的。
输出
你的程序必须输出施展磁化法术所需的最小数量,以移除所有魔法方块。
示例输入 1
3 26 29 9 12 6 10 15 16 8 17 18 19
样本输入 1 的输出
1
示例输入 2
3 2 10 1 11 5 18 9 16 12 19 15 20
样本输入 2 的输出
2
示例输入 3
6 2 8 1 14 6 16 3 10 3 20 11 13 17 28 18 21 22 29 25 31 23 24 33 34
样本输入 3 的输出
2