Preparing NOJ

最长k可重区间集问题

1000ms 65536K

Description:

 给定实直线Ln个开区间组成的集合I,和一个正整数k,试设计一个算法,从开区间集合I 中选取出开区间集合SÍI,使得在实直线L的任何一点xS 中包含点x 的开区间个数不超过k,且                                                       

 

达到最大。这样的集合S称为开区间集合I的最长k可重区间集。

称为最长k可重区间集的长度。

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

 

Input:

 

文件的第1 行有2 个正整数nk,分别表示开区间的个数和开区间的可重迭数。接下来的n行,每行有2个整数,表示开区间的左右端点坐标。

Output:

  程序运行结束时,将计算出的最长k可重区间集的长度输出。

Sample Input:

4 2
1 7
6 8
7 10
9 13

Sample Output:

15

Note:

 

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1368

Tags

Submitted 3

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet