首页 > 试题广场 >

精华帖子

[编程题]精华帖子
  • 热度指数:98 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小红书的推荐帖子列表为[0,n],其中所有的帖子初始状态为”普通“,现在运营同学把其中的一些帖子区间标记为了”精华“。
现在运营同学希望截取一段长度为k的帖子区间,使得这一区间内精华部分的帖子数量尽可能的多。
请你帮运营同学求出长度为k区间最多的精华帖子数量。



输入描述:
第一行输入两个正整数n,m,k,代表初始帖子列表长度,精华区间的数量,以及运营同学准备截取的长度。
接下来的m行,每行输入两个正整数li,ri,代表第i个区间。
1 ≤ k ≤ n ≤ 1000000000
1 ≤ m ≤ 100000
0 ≤ li < ri ≤ n
保证任意两个区间是不重叠的。



输出描述:
一个正整数,代表最多的精华帖子数量。
示例1

输入

5 2 3
1 2
3 5

输出

2

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