思路:贪心算法。
和上一道 线段覆盖问题简直异曲同工之妙,只不过在判断是否有交集的时候多一步,左端点==有端点的操作就好。因为,在这一时刻,我们假定换台是不需要浪费时间的,,,
# include<cstdio> # include<iostream> # include<algorithm> using namespace std; struct node { int a,b; }x[106]; int cmp( node x1,node x2 ) { return x1.b <= x2.b; } int main ( void ) { int n; while ( cin>>n&&n!=0 ) { for ( int i = 1;i <= n;i++ ) { cin>>x[i].a>>x[i].b; } sort(x,x+n,cmp); int ans = 0; int max = -1; for ( int i = 1;i <= n;i++ ) { if ( x[i].a >= max ) { ans++; max = x[i].b; } } cout<<ans<<endl; } return 0; }