2012-0043

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

本题目抽象成模型就是：给定若干区间，选取尽可能少的点，覆盖所有的区间（使得每个区间至少包含其中的一个点）。最简单的做法就是贪婪。先把所有的区间排序（注意记录原始的index），排序规则是：先按右端点排，大的排在后面，如果右端点相同的，再按左端点排，大的排在后面。然后从左到右遍历。因为是整数区间，我们可以在读入区间的时候，把右端点减1得到闭区间方便后来处理。然后选取第一个区间的右端点。接着往右走，遇到点在区间内的，就安排在同一天。如果不在的，选取当前区间的右端点继续向右扫描，且开始新的一天考试。

本题目抽象成模型就是：给定若干区间，选取尽可能少的点，覆盖所有的区间（使得每个区间至少包含其中的一个点）。最简单的做法就是贪婪。先把所有的区间排序（注意记录原始的index），排序规则是：先按右端点排，大的排在后面，如果右端点相同的，再按左端点排，大的排在后面。然后从左到右遍历。因为是整数区间，我们可以在读入区间的时候，把右端点减1得到闭区间方便后来处理。然后选取第一个区间的右端点。接着往右走，遇到点在区间内的，就安排在同一天。如果不在的，选取当前区间的右端点继续向右扫描，且开始新的一天考试。