A7221 | $雾港实验室的高压服务器$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

雾港实验室有两座数据中心 A 与 B 。现在有 $n$ 个任务最初都运行在 A 上。 第 $i$ 个任务的运行时间是一个 闭区间 $[l_i,r_i]$：表示从时刻 $l_i$ 开始到时刻 $r_i$ 结束（两端都算在运行中）。 你需要把任务逐步迁移到 B 。迁移规则如下： * 在任意时刻 $t$，你可以选择任意多个 此刻正在运行且仍在 A 上 的任务，把它们从 A 迁移到 B ； * 迁移是 瞬时完成 的，不会改变任务的 $[l_i,r_i]$； * 一个任务一旦迁移到 B ，就会在 B 上运行到结束，不会再回到 A ； * 你总共最多只能迁移 $K$ 个任务（可以少于 $K$ 个）。 定义任意时刻 $t$ 数据中心 A 的压力为：此刻仍在 A 上运行的任务数量。 你希望设计迁移方案，使得整个时间轴上 A 的 最大压力 尽量小。 请输出这个最小可能的“峰值压力”。

第一行两个整数 $n,K$。 接下来 $n$ 行，每行两个整数 $l_i,r_i$，表示第 $i$ 个任务的运行区间。

输出一个整数，表示最小可能的峰值压力。

输入 #1

输出 #1

样例解释 如果迁移任务 $[2,6]$ 与 $[4,7]$，那么留在 A 上的是 $[1,4]、[3,5]、[1,2]、[6,6]$。 此时在时刻 $3$，A 上同时运行的任务为 $[1,4]、[3,5]$（共 $2$ 个）；其他时刻也不会超过 $2$，所以峰值压力可以做到 $2$。 数据范围与测试点 * $1\le n\le200000$ * $0\le K\le n$ * $1\le l_i\le r_i\le10^9$ 测试点编号$n$ 上界$1\sim4$$n\le20$$5\sim10$$n\le10000$$11\sim20$$n\le200000$

C++ 编辑器

输入

输出