Responsive image

问题 A: 区间问题

问题 A: 区间问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 2  解决: 26
[提交][状态][讨论版][命题人:]

题目描述

有n项工作,每项工作分别在si时间开始,在ti时间结束。对于每项工作,你都可以选择参与与否。如果选择了参与,那么自始至终都必须全程参与。此外,参与工作的时间段不能重叠(即使是开始与结束的瞬间重叠也是不允许的)。

你的目标是参与尽可能多的工作,那么最多能参与多少项工作呢?1<=n<=100000,1<=si<=ti<=10^9。

输入描述

n

输出描述

最多参与的工作项数

样例输入

3

5 20

14 17

8 11

样例输出

2

提示


(1)在可选的工作中,每次都选取开始时间最早的工作



(2)在可选的工作中,每次都选取结束时间最早的工作



(3)在可选的工作中,每次都选取用时最短的工作



(4)在可选的工作中,每次都选取与最少可选工作有重叠的工作



此问题可通过贪心算法求解,关键在于对上述贪心策略的选择

[提交][状态]
ACM算法攻关部