2215. 传令兵部署
1000ms
256MB
简单
贪心算法
题目描述
某红军部队接到命令，需在多个防区内部署传令兵，确保每个防区至少有一名传令兵驻扎（一个传令兵也可兼顾多个防区）。传令兵数量有限，要求用最少的传令兵覆盖所有防区。
现有 n 个防区，每个防区的起点为 Li，终点为 Li + leni（覆盖闭区间 [Li, Li+leni]）。输出最少需要的传令兵数量。
现有 n 个防区，每个防区的起点为 Li，终点为 Li + leni（覆盖闭区间 [Li, Li+leni]）。输出最少需要的传令兵数量。
输入格式
输入共 n+1 行：
1. 第1行：1个整数 n，表示防区个数
2. 第 2 - n+1 行：每行2个整数 Li, leni，代表每个防区的起点和长度
1. 第1行：1个整数 n，表示防区个数
2. 第 2 - n+1 行：每行2个整数 Li, leni，代表每个防区的起点和长度
输出格式
输出1行，1个整数：最少需要的传令兵数量
样例 1
输入 (Input)
5 1 2 3 3 5 2 8 3 11 1
输出 (Output)
3
样例 2
输入 (Input)
6 1 1 3 2 6 1 9 2 12 1 15 2
输出 (Output)
6
样例 3
输入 (Input)
5 8 2 3 1 1 2 12 1 6 3
输出 (Output)
3
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功