当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6808:Go Running

题目描述
Zhang3 is the class leader. Recently she's implementing a policy about long-distance running. This forces every student in her class to take a run.

There is a main road in the school from west to east, which can be regarded as an infinite axis, and its positive direction is east. Positions on the road are represented with numbers. In order to complete the task, each student must run along the main road. Each student can decide the following things:

- The time to start running.
- The time to finish running.
- The position to start running.
- The direction of running, which is either west or east.

Once these things are decided, the student will appear at the starting position on the road at the start time, then start running in the chosen direction at a speed of $1 \; \text{m/s}$. The student disappears at the finish time. Each student will only run once.

Zhang3 knows that some students are not following her policy, so she set up some monitors. According to technical issues, the monitors can only report that there's at least one student at a certain place at a certain time. Finally Zhang3 received $n$ reports.

Help Zhang3 determine the minimum possible number of students who have run.
输入解释
The first line of the input gives the number of test cases, $T \; (1 \le T \le 100)$. $T$ test cases follow.

For each test case, the first line contains an integer $n \; (1 \le n \le 10^5)$, the number of reports.

Then $n$ lines follow, the $i ^ \mathrm{th}$ of which contains two integers $t_i, x_i \; (1 \le t_i, x_i \le 10^9)$, representing that there's at least one student at position $x_i \; \text{(m)}$ at time $t_i \; \text{(s)}$.

The sum of $n$ in all test cases doesn't exceed $5 \times 10^5$.
输出解释
For each test case, print a line with an integer, representing the minimum number of students who have run.
输入样例
2
3
1 1
2 2
3 1
3
1 1
2 2
3 3
输出样例
2
1
来自杭电HDUOJ的附加信息
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6808

最后修改于 2020-10-25T23:34:34+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
10000/5000MS(Java/Others) 524288/524288K(Java/Others)