问题分析
-
区间选点问题：在数轴上选择最少的点，使得每个区间内至少有一个点。
-
最大不相交区间数量问题：选择最多的区间，使得这些区间两两之间没有交集。
等价性证明
-
必要性：假设存在一个最优的区间选点方案，选点数量为 m。每个点可以覆盖若干个区间，这些区间构成一个不相交的集合（因为如果有两个区间相交，它们不能被同一个点覆盖）。因此，最大不相交区间的数量至少为 m。
-
充分性：假设存在一个最大不相交区间集合，大小为 k。我们可以在每个区间的右端点放置一个点，这些点可以覆盖所有区间（否则存在某个区间与所有选中的区间不相交，与最大性矛盾）。因此，选点数量最多为 k。
综上，最大不相交区间的数量等于最少的选点数量，即 $m = k$。
