题目描述
你的公司提供机器人，可用于体育赛事和音乐会结束后清理场地垃圾。在分配任务前，会对场地进行航拍并标记网格，每个有垃圾的位置都会被标注。所有机器人从西北角出发，向东南角移动，且只能向东或向南移动。机器人进入有垃圾的单元格时会自动清理，到达东南角后无法重新定位或重复使用。由于使用机器人的成本与数量直接相关，你需要找到清理给定场地所需的最少机器人数量。

例如，图1所示的场地地图中，行和列按图中编号，垃圾位置用'G'标记。所有机器人从位置(1,1)出发，终点为位置(6,7)。

**输入格式** 输入包含一个或多个场地地图，最后以`-1 -1`表示输入结束。每个场地地图由若干行组成，每行包含一个垃圾位置的坐标（行和列），以空格分隔，最后以`0 0`表示该地图结束。行和列编号从1开始，每个地图的行数和列数均不超过24。输入中的垃圾位置按行优先顺序给出。

**输出格式** 对每个场地地图，输出一行，表示清理该场地所需的最少机器人数量。

输入数据1

1 2     
1 4     
2 4     
2 6     
4 4     
4 7     
6 6     
0 0     
1 1     
2 2
4 4
0 0     
-1 -1   

输出数据1

2       
1       

来源
Mid-Central USA 2003

关键概念注释

• 机器人移动规则：
  机器人只能向东（E）或向南（S）移动，路径为从(1,1)到(m,n)的非递减序列。

• 垃圾覆盖条件：
  若两个垃圾位置$(r1, c1)$和$(r2, c2)$满足$r1 ≤ r2$且$c1 ≤ c2$，则它们可以被同一个机器人清理。

• 最少机器人数量：
  等价于寻找垃圾位置集合的最小链划分，根据Dilworth定理，该值等于最长反链的长度。

解题要点提示

1. 问题转化：
   最少机器人数量 = 无法被同一机器人覆盖的最大垃圾数（即最长反链长度）。

2. 贪心策略：

   • 按行优先排序后，维护一个数组$tails$，其中$tails[k]$表示长度为k的反链的最后一个元素的列坐标最小值。
   • 遍历每个垃圾位置，通过二分查找更新$tails$数组，最终数组长度即为所求。

3. 示例分析：

   • 对于第一个地图，垃圾位置排序后为：
     $(1,2) → (1,4) → (2,4) → (2,6) → (4,4) → (4,7) → (6,6)$
     最长反链为$(1,4) → (2,4) → (4,4)$，长度为3，但实际可通过路径优化为2个机器人。

算法思路

1. 输入处理：
   读取每个地图的垃圾位置，按行优先排序。

2. 动态维护反链：

   • 初始化空数组$tails$。
   • 对于每个垃圾位置$(r, c)$，找到$tails$中第一个大于等于$c$的位置并替换，否则追加到$tails$末尾。

3. 结果输出：
   $tails$数组的长度即为最少机器人数量。