2931. 最长k可重区间集问题

单点时限: 2.0 sec

内存限制: 256 MB

给定实直线 L 上 n 个开区间组成的集合 I,和一个正整数 k,试设计一个算法,从开区间集合 I 中选取出开区间集合 S 包含于 I,使得在实直线 L 的任何一点 x,S 中包含点 x 的开区间个数不超过 k,且 S 中的区间长度之和达到最大。这样的集合 S 称为开区间集合 I 的最长 k 可重区间集。S 中的区间长度之和最大值称为最长 k 可重区间集的长度。

对于给定的开区间集合 I 和正整数 k,计算开区间集合 I 的最长 k 可重区间集的长度。

输入格式

第 1 行有 2 个正整数 n (n<600)和 k,分别表示开区间的

个数和开区间的可重迭数。接下来的 n 行,每行有 2 个整数,表示开区间的左右端点坐标。

输出格式

将计算出的最长 k 可重区间集的长度输出

样例

Input
4 2
1 7
6 8
7 10
9 13
Output
15

4 人解决,7 人已尝试。

4 份提交通过,共有 12 份提交。

7.9 EMB 奖励。

创建: 14 年,2 月前.

修改: 2 年,7 月前.

最后提交: 4 月,1 周前.

来源: zzz-周正中

题目标签