最近在算法课上学到了贪心算法，老师布置了这个“选点问题”。题目要求在数轴上选最少的点，使得每个给定区间都至少包含一个点。
我一开始试着画了几个例子。比如给三个区间：[1,3]、[2,4]、[3,5]。如果随便选点，可能在1、2、3各放一个点，用了三个点。但仔细观察，其实选点3就能覆盖所有区间。这让我开始思考，有没有一种系统的方法，总能找到最少的点数？
我尝试了好几种思路。先试了按左端点排序：从最左边的区间开始，在它的右端点放点。但很快就发现有问题，比如区间[1,4]和[2,3]，按左端点排序会先在4放点，但其实在3放点更好。又试了按区间长度排序，先处理短的区间，但也不对。
最后试了按右端点排序，画了几个例子发现都得到了正确答案。策略很简单：先把所有区间按照右端点从小到大排好，然后从第一个区间开始，在它的右端点放一个点。接着看下一个区间，如果这个点已经落在下一个区间里，就跳过；如果不落在里面，就在下一个区间的右端点再放一个新点。如此重复下去。
但为什么这样是对的呢？我需要证明这种贪心选择是合理的。假设我们按右端点排序后，第一个区间是[a₁, b₁]。我选择在b₁放点。现在假设存在某个最优解，它覆盖这个区间的点是p（p在[a₁, b₁]内）。如果p不等于b₁，我们可以把p换成b₁。因为b₁≥p，所以b₁仍然在第一个区间内，而且对于后面那些原本被p覆盖的区间，由于它们的右端点都≥b₁，所以b₁很可能也能覆盖它们，至少不会让情况变差。这说明一定存在一个包含b₁的最优解。这样一步一步推下去，每个选择都是“安全”的。
用C++实现起来很简洁。先读入n个区间，存成pair数组，然后按右端点排序。用一个变量last_point记录上一个选择的点，初始设成很小的数。遍历排序后的区间，如果last_point小于当前区间的左端点，说明需要新点，就在当前区间右端点放点，计数器加一。
时间复杂度主要是排序的O(n log n)，遍历是O(n)，总的是O(n log n)。空间上除了存区间数组，只需要几个变量。
通过这个题目，我对贪心算法有了更深的理解。贪心不是瞎猜，而是基于问题特性做出局部最优的选择，并且要能证明这样的选择不会破坏得到全局最优解的可能性。有时候贪心解法很简单高效，但并非所有问题都能用贪心。关键是要找到那种“当前最好的选择不会让未来无路可走”的问题特征。在实际编程中，贪心算法往往代码简洁，运行效率高，是很实用的算法思想。