Meeting Room Allocation

 

#include <stdio.h>
#include <algorithm>
#define N 100000

using namespace std;

int n;
struct _tuple{
    int st;
    int en;
};
_tuple A[N+1];

void input(){
    //freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d %d",&A[i].st,&A[i].en);   
    }
}

bool sf(_tuple a,_tuple b){
    if(a.en==b.en){
        return a.st<b.st;
    }
    return a.en<b.en;
}

int main(){
    input();
    sort(A,A+n,sf);
    int num=1;
    int tmp=A[0].en;
    for(int i=1;i<n;i++){
        if(A[i].st>=tmp){
            tmp=A[i].en;
            num++;
        }
    }
    printf("%d",num);
}