贪心证明
（看了讲解视频后自己又琢磨了一下，感觉y总的证明好像跳了一步，这里写下我对于本题的贪心证明，希望能帮到各位！）
设 ans 为最优解， cnt为某一个答案。
欲证：ans = cnt
① ans <= cnt， 显然；
② ans >= cnt， 这里应该是容易产生困惑的地方。
首先要清楚一点，ans是一个定值、常数，表示最优解的值； 而cnt它是一个变量，代表某一种方案的值。
要证: ans >= cnt， 只需要证：ans >= max(cnt)即可，因为如果连最大的cnt都不超过ans，那么所有的cnt都小于等于ans。
何时取到max？当全部区间两两不相交时，cnt必然取到最大值。（但是，有部分区间相交时，也可以取到最大值，设想一下只有2个区间，中间相交了一小部分，我们可以分别取第一个区间的最左，和第二个区间的最右。但这并不重要，只要我们能证明，在其中一种取到最大值的方案中，ans >= cnt，那么剩下的全部方案的cnt必然小于等于ans。）
显然，当全部区间两两不相交时，ans = cnt。
因此由ans >= max(cnt) >= cnt， 可证②也是成立的。
综上所述，由①②可知，ans = cnt。
大家都证明得很牵强，让我也来证明一下，如果有问题，欢迎指出。疑惑点在ans>=cnt，我们可以假设有ans小于cnt，且咋们用算法求出来的区间用数组t表示。那么这个ans肯定要包含咋们算法求出来的区间。那这个ans可不可能有个区间包含了咋们求出来的区间t的两个区间呢。显然不可能，这是算法证明的关键。因为如果有这么一个区间的话，咋们贪心算法肯定能找出来，那么t区间就不是咋们算法求解出来的区间了。所以ans连我们数组t都包含不了，他还想包含全部，简直想屁吃。
大家可以在纸上画一个区间，包含数组t区间，想看看到底可不可能，如果可能 请打死我。
大佬写得太棒了， 这是我看前面几个题解写得最清楚的一个
谢谢大佬！
【1，4】【3，6】，cnt的一个解为（1，5），而ans为（4）。cnt>=ans。所以，cnt不是某一个答案，应该是这个算法的某一个答案。
您好，关于最后 得出的 ans >= max(cnt) >= cnt 感觉有点问题，应该是 ans = max(cnt) >=cnt
你前面写的很好，但是cnt的定义你还是弄错了。它确实是一个变量，也确实是代表可行方案中的某个值。但是它是无穷大的。我不管题目到底给了多少个区间，我就让每个区间都给上一个点，并且我还可以在任意个区间上加上任意点，都满足可行方案的要求。那么cnt就是无穷大的。①是绝对成立的，但是②就是错的。你要想让②对，你的cnt的定义就和①的cnt的定义不一样了。
我不是大佬，我是蒟蒻。我也不知道怎么证明。。我只是感觉这证明有点强行证明的意思。虽然我能懂y总的意思。但我还是感觉这是伪证。
嗯 我也感觉cnt 的定义是改变了的
这里的cnt并不是 所有的可行方案，而是我们根据算法可以得出的方案。因为我们要验证的是我们的算法得出的方案，而不是所有方案。 因此方案的不是无穷大的， 方案的值域为[1, n]
太棒了
我感觉这个题是要证明 “按最右边排序然后有空白区间res++” 这种方案是最优， 即这种方案的cnt==ans（ans代表最优方案）
那么max（cnt） 应该代表的是各种方案中cnt的最大值，所以要控制区间状态，找到不同方案的最大值。
而不是举出 在极端状态下，最右边排序方案的cnt，这样好像没有什么意义
希望可以和大佬们讨论讨论
我想，应该是不是说全部区间两两不相交，而是说cnt代表了那些全部区间中不相交的区间，，cnt不能再少了，最优解一定大于等于cnt
对，应该是你说的这样，并不是全部区间两两不相交，只是通过遍历从小到大的右端点，把那些不相交的区间挑出来了，而这些不相交的区间的个数是cnt个，把这些区间都覆盖掉至少需要cnt个点，所以ans>=cnt，而那些相交的区间显然就不用算了，全都包含在这些不相交的区间内了
yep!
我还是觉得有点问题, 这里不相交的区间个数是cnt个需要至少cnt个点, 而根据ans的逻辑(取点为前面某个区间的右端点, 如果当前区间有overlap则跳过) 此时ans == cnt; 但是证明的第一步是证最优解是可行解, 即ans<=cnt, 所以现在只证明了ans<=cnt且可以取等号, 并没有证明ans >= cnt.
y总的证明是错的，cnt的定义变了。在②的情况下，cnt的定义变成了某个特定的可行方案，并且这个特定的可行方案的值刚好就是最小值。
cnt 表示的采取贪心策略后的值，方案是yxc提出的右端点方案，你说的 不同方案的最大值这个说法应该是不太对的样子，cnt就应该是采取某种特定方案后的 结果值，只不过要证明的是这个结果值大等于最优解（显然），和小等于最优解。（采取最极端的cnt的区间，都小等于res）
我在想直接假设其为最优解。然后得出ans≥cnt的严谨性。。。这好像是由结果倒推，一般这样操作是反证法吧。。。
关键 谢谢带佬