I - Restaurant
A restaurant received n orders for the rental. Each rental order reserve the restaurant for a continuous period of time, the i-th order is characterized by two time values — the start time li and the finish time ri (li?≤?ri).
Restaurant management can accept and reject orders. What is the maximal number of orders the restaurant can accept?
No two accepted orders can intersect, i.e. they can't share even a moment of time. If one order ends in the moment other starts, they can't be accepted both.
Input
The first line contains integer number n (1?≤?n?≤?5·105) — number of orders. The following n lines contain integer values li and ri each (1?≤?li?≤?ri?≤?109).
Output
Print the maximal number of orders that can be accepted.
Example
Input
2 7 11 4 7
Output
1
Input
5 1 2 2 3 3 4 4 5 5 6
Output
3
Input
6 4 8 1 5 4 7 2 5 1 3 6 8
Output
2
#include<stdio.h> #include<algorithm> using namespace std; struct Fuck {int sta;int end; }a[500000+10]; bool cao(Fuck a,Fuck b) {if(a.end == b.end )return a.sta > b.sta;elsereturn a.end < b.end; } int main() {int n;while( ~scanf("%d",&n) ){for(int i=0;i<n;i++)scanf("%d %d",&a[i].sta,&a[i].end);sort(a,a+n,cao);int t=a[0].end,sum=1; for(int i=0;i<n;i++){if(a[i].sta>t){sum++;t=a[i].end;}}printf("%d\n",sum);}return 0;}