证明 ans=cnt

• 假设ans是最优解，表示最多有ans个不相交的区间；cnt是可行解，表示算法求出cnt个不相交的区间，显然有ans≥cnt

• 反证法证明ans≤cnt。假设ans>cnt，由最优解的含义知，最多有ans个不相交的区间，因此至少需要ans个点才能覆盖所有区间，而根据算法知，只需cnt个点就能覆盖全部区间，且cnt<ans，这与前边分析至少需要ans个点才能覆盖所有区间相矛盾，故ans≤cnt

• 综上所述ans=cnt

代码略：因为和上一道题 【905区间选点】 https://www.acwing.com/solution/content/38128/ 完全一样