3169: 15_C : Activity Selection Problem

$0.00\%$ 下一题

Time Limit	$1$ 秒/Second(s)	Memory Limit	$512$ 兆字节/Megabyte(s)
提交总数	$0$	正确数量	$0$
裁判形式	标准裁判/Standard Judge	我的状态	尚未尝试
难度		分类标签	STL

Description

Activity Selection Problem

There are $n$ acitivities with start times $\{s_i\}$ and finish times $\{t_i\}$ . Assuming that a person can only work on a single activity at a time, find the maximum number of activities that can be performed by a single person.

Input

$n$ $s_{1}$ $t_{1}$ $s_{2}$ $t_{2}$ : $s_{n}$ $t_{n}$

The first line consists of the integer $n$ . In the following $n$ lines, the start time $s_{i}$ and the finish time $t_{i}$ of the activity $i$ are given.

Output

Print the maximum number of activities in a line.

Sample Input复制

Sample Output复制

提示

Constraints

$1 \leq n \leq 10^{5}$
$1 \leq s_{i} < t_{i} \leq 10^{9} (1 \leq i \leq n)$

赛题来源/所属竞赛会津大学《挑战数据结构与算法》挑战数据结构与算法

竞赛编号	竞赛名称	竞赛时间	访问比赛

AOJ

祝同学们学习进步，编程快乐！

Please Login

本题记录	用户（点击查看用户）	运行号（点击购买题解）	时间
算法最快[ms]
内存最少[KB]
第一AC
第一挑战