（3） 最少冲突的活动优先， 既然上面安排活动是想减少冲突，那么如果我们优先安排冲突最少的活动可以么？至少从（1）和（2）看来，这个策略是有效的。真是对的么？ 尝试这个例子：
[0,2) [2,4) [4,6) [6,8) [1,3) [1,3) [1,3) [3,5) [5,7) [5,7) [5,7) 看一下[0,2) 和3个活动冲突——3个[1,3) [2,4)和4个活动冲突3个[1,3)和一个[3,5) [4,6)和也和4个活动冲突3个[5,7)和一个[3,5) [6,8)和3个活动冲突——3个[5,7) 下面[1,3)和[5,7)每个都和5个活动冲突， 而[3,5)只和两个活动冲突——[2,4)和[4,6)。 那按照我们的策略应该先安排[3,5), 可是一旦选择了[3,5)，我们最多只可能安排3个活动。 但明显第一行的4个活动都可以安排下来，所以这种策略也是不对的。 （4） 看似最不对的策略——结束时间越早的活动优先。这个策略是有效的，我们可以证明。假设最优解OPT中安排了m个活动，我们把这些活动也按照结束时间由小到大排序，显然是不冲突的。假设排好顺序后，这些活动是a(1) , a(2), a(3)….am 假设按照我们的贪心策略，选出的活动自然是按照结束时间排好顺序的，并且也都是不冲突的，这些活动是b(1), b(2) …b(n) 问题关键是，假设a(1) = b(1), a(2) = b(2)…. a(k) = b(k)，但是a(k+1) != b(k+1)，回答几个问题： (1) b(k+1)会在a(k+2), a(k+3), …. a(m)中出现么？ 不会。因为b(k+1)的结束时间是最早的，即f(b(k+1)) <= f(a(k+1)),而a(k+2), a(k+3), …. a(m)的开始时间和结束时间都在f(a(k+1))之后，所以b(k+1)不在其中。 (2) b(k+1)和a(1), a(2), …. a(k) 冲突么？ 不冲突，因为a(1), a(2), …. a(k)就是b(1), b(2), …. b(k) (3) b(k+1)和a(k+2), a(k+3), …. a(m)冲突么？ 不冲突，因为f(b(k+1)) <= f(a(k+1))，而a(k+2), a(k+3), …. a(m)的开始时间都在f(a(k+1))之后，更在f(b(k+1))之后。 因此我们可以把a(k+1) 换成b(k+1)， 从而最优解和我们贪心得到的解多了一个相同的，经过一个一个替换，我们可以把最优解完全替换成我们贪心策略得到的解。 从而证明了这个贪心策略的最优性。最后，我们来提供输入输出数据，由你来写一段程序，实现这个算法，只有写出了正确的程序，才能继续后面的课程。 输入 第1行：1个数N，线段的数量(2 <= N <= 10000) 第2 - N + 1行：每行2个数，线段的起点和终点(-10^9 <= S,E <= 10^9) 输出 输出最多可以选择的线段数量。 输入示例 3 1 5 2 3 3 6 输出示例 2 请选取你熟悉的语言，并在下面的代码框中完成你的程序，注意数据范围，最终结果会造成Int32溢出，这样会输出错误的答案。 const int maxn=1e4+10; struct node { int x,y; bool operator<(const node & a)const { return y<a.y; } }a[maxn]; int main() { ios::sync_with_stdio(false); int n,k,ans; while(cin>>n) { ans=1; for(int i=0;i<n;i++)cin>>a[i].x>>a[i].y; sort(a,a+n); k=a[0].y; for(int i=1;i<n;i++) if(k<=a[i].x) { ans++; k=a[i].y; } cout<<ans<<endl; } return 0; }