跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0253. #6014. 「网络流 24 题」最长 k 可重区间集

  • ID: 259
  • 传统题
  • 1000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 网络流
  • 图论
  • 难度待定
  • 难度
  • 共享题库
  • LibreOJ
  • 中文题面
  • 题目来源
  • 题面语言

#6014. 「网络流 24 题」最长 k 可重区间集

题目描述

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

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

输入格式

文件的第 行有 个正整数 和 ,分别表示开区间的个数和开区间的可重迭数。
接下来的 行,每行有 个整数 和 ,表示开区间的左右端点坐标,注意可能有 ,此时请将其交换。

输出格式

输出最长 可重区间集的长度。

样例

样例输入

4 2
1 7
6 8
7 10
9 13

样例输出

15

数据范围与提示


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 145 题。保留原作者与原赛事署名。