首页 > 试题广场 >

植树节

[编程题]植树节
  • 热度指数：44 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}植树节即将来临，学校决定组织志愿者为一排编号从 0 开始、向右无限延伸的树苗浇水。
\hspace{15pt}共有 n 名志愿者，第 i 名志愿者选择了闭区间 [a_i,b_i]，并为区间内的每一棵树苗各浇一次水。
\hspace{15pt}所有志愿者完成任务后，某些树苗可能被多名志愿者重复浇水，而另一些树苗一次也没有被浇水。
\hspace{15pt}请你计算被浇水次数最多的树苗最终被浇了多少次。

输入描述:
\hspace{15pt}在一行上输入一个整数 n\left(1\leqq n\leqq 10^5\right)，表示志愿者数量。 
\hspace{15pt}此后 n 行，第 i 行输入两个整数 a_i,b_i\ \left(0\leqq a_i\leqq b_i\leqq 10^6\right)，表示第 i 名志愿者浇水的树苗编号区间。


输出描述:
\hspace{15pt}输出一行一个整数，表示被浇水次数最多的树苗被浇水的次数。
示例1

输入

4
0 2
2 4
1 4
6 7

输出

3

说明

\hspace{15pt}在该样例中： 
\hspace{23pt}\bullet\,区间 [0,2] 覆盖树苗 \{0,1,2\}； 
\hspace{23pt}\bullet\,区间 [2,4] 覆盖树苗 \{2,3,4\}； 
\hspace{23pt}\bullet\,区间 [1,4] 覆盖树苗 \{1,2,3,4\}； 
\hspace{23pt}\bullet\,区间 [6,7] 覆盖树苗 \{6,7\}。 
\hspace{15pt}最终树苗 2 被浇水 3 次，为最大值，故输出 3。
示例2

输入

4
1000000 1000000
1000000 1000000
0 1000000
1 1000000

输出

4

说明

\hspace{15pt}在该样例中，编号为 10^6 的树苗被四名志愿者同时浇水，故答案为 4。
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 16浏览

热门推荐

相关试题

植树节

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号