测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A6955. 饥饿的奶牛

编程题 普及+/提高

题目描述

有一条奶牛冲出了围栏,来到了一处圣地(对于奶牛来说),上面用牛语写着一段文字。

现用汉语翻译为:

有 $N$ 个区间,每个区间 $x,y$ 表示提供的 $x\sim y$ 共 $y-x+1$ 堆优质牧草。你可以选择任意区间但不能有重复的部分。

对于奶牛来说,自然是吃的越多越好,然而奶牛智商有限,现在请你帮助他。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行,每行两个数 $x,y$,描述一个区间。

输出格式

输出最多能吃到的牧草堆数。

输入输出样例

输入 #1
3
1 3
7 8
3 4
输出 #1
5

说明/提示

## 数据范围
$1 \leq n \leq 1.5 \times 10^5$,$0 \leq x \leq y \leq 3 \times 10^6$。

## 样例分析

**可选区间及收益(长度):**
1. [1, 3]:收益 $3 - 1 + 1 = \mathbf{3}$
2. [7, 8]:收益 $8 - 7 + 1 = \mathbf{2}$
3. [3, 4]:收益 $4 - 3 + 1 = \mathbf{2}$

**冲突判断:**
* 区间 [1, 3][3, 4] 在位置 **3** 重叠,**不能同时选**。
* 区间 [7, 8] 离得很远,跟谁都不冲突,**必选**(收益 +2)。

**决策比较:**
* **方案 A**:选 [1, 3] + [7, 8] $\rightarrow$ 总收益 $3 + 2 = \mathbf{5}$
* **方案 B**:选 [3, 4] + [7, 8] $\rightarrow$ 总收益 $2 + 2 = 4$

**结论:**
方案 A 收益最大,输出 **5**。
上一题 去做题 下一题