NOI2016 DAY2：区间选择最小花费问题

NOI2016（中国国家青少年信息学奥林匹克竞赛）的第二天竞赛中，有一个传统型题目叫做“区间”（Interval），其主要涉及了数轴上的区间选择问题。给定的数轴上有 n 个闭区间 [l1, r1], [l2, r2], ..., [ln, rn]，参赛者的目标是从这些区间中选择 m 个（1 <= m <= n），使得这些区间共同包含至少一个公共点 x，即满足 l1 <= x <= r1, l2 <= x <= r2, ..., ln <= x <= rn。 每个区间 [li, ri] 的长度定义为 ri - li。题目要求找到所有合法的选择方案中，花费最小的方案。合法方案的花费是指被选中区间中最长的长度与最短长度之差。若不存在这样的合法方案，则输出 -1。 输入格式： - 文件 interval.in 包含两行： - 第一行是两个正整数 n 和 m，分别代表区间数量和需要选择的区间数量。 - 接下来的 n 行，每行包含两个整数 l 和 r，表示一个区间的左右端点，l <= r。 输出格式： - 文件 interval.out 仅有一行，输出最小花费，如果不存在合法方案则输出 -1。 这个题目考察了参赛者对数据结构（如区间树、优先队列）以及算法分析（如贪心策略或动态规划）的理解，特别是如何高效地查找区间覆盖的问题。对于编程挑战，需要编写针对 C++、C 或 Pascal 语言的代码来实现算法，并且注意使用提供的编译开关优化性能，内存限制为 256MB，每个测试点有严格的时限要求（3秒、1.5秒和 N/A，取决于题目类型）。 在解答这类问题时，可能需要用到区间树（如 R-tree 或 segment tree）来存储和查询区间，通过合并操作找出最优解。同时，还需要考虑如何处理大规模输入（n 可能很大），确保算法的时间复杂度在规定时间内完成计算。在提交源程序时，需确保正确地添加了对应的后缀（如 .cpp、.c 或 .pas）。 这是一道既考验基础算法能力又需要实际编程技巧的题目，参赛者需要具备扎实的数学思维和编程素养来解决这一问题。