题解

//区间选线段问题

用每个线段后半段从小到大排序，再用首指针判断后一段首点能否超过前段后点，从开头找到最后即可

O(N)算法

#include<iostream> 
#include<algorithm> 
using namespace std; 

struct node{ 
int x, y;  
}a[1005]; 

bool cmp(node a , node b){ 
return a.y <  b.y; 
} 
int n , ans = 0 ; 

int main(){ 
cin >> n; 
int i , j; 
 
for(i = 1 ;i <= n;i++){ 
 cin >> a[i].x >> a[i].y; 
} 
 
sort(a + 1 , a + n + 1 , cmp); 
 
 
int k = a[1].y; 
ans ++; 
for(i = 2;i <= n;i++){ 
  
 if(a[i].x >= k) 
 { 
  ans++; 
  k = a[i].y; 
 } 
  
} 
 
cout << ans << endl; 
return 0; 
}

//第一次写题解（-~-）