浅谈一些有趣的区间问题

本篇随笔浅谈一下算法竞赛中一些有趣的区间问题。

一、最短区间点覆盖

给定一些点，用不超过\(m\)个区间将其全部覆盖，要求区间长度最短。

解决方法：

考虑\(m\)的限制，显然，\(n\)个区间就可以使得其全部覆盖，区间总长度为0.所以\(m\)一定比\(n\)小，否则没有意义。

正向思考不是很容易。我们反着来。

现在只有一个区间包含了所有的点。现在我们要拆成两个区间，那么这个就变成了一个断边的过程。根据贪心，每次肯定要断掉一个最长的线段。

以此类推，直到\(m\)都用完即可。

二、最少区间数区间覆盖

给定一个大区间和一堆大区间的子区间，需要从中挑选出最少的区间来全部覆盖这个大区间，可以重复覆盖。

解决方法，还是贪心，看看一个区间能最广拓展到哪个点，以此类推。