/*
* Problem :: 1931 / 회의실 배정
*
* Kind :: Greedy
*
* Insight
* - Greedy 의 가장 대표적인 문제
* + 빨리 시작하는 순서대로 회의를 배정할까?
* # |-----------------------|
* |-| |-| |-| |-| |-| |-|
* + 시간이 적게 걸리는 회의 순서대로 회의를 배정할까?
* # |--|
* |---||---|
* + 빨리 끝나는 순서대로 회의를 배정할까?
* # ...아무리 생각해도 반례가 없다
* -> 빨리 끝나는 순서대로 회의를 배정했을 때
* 배정된 회의의 순서를 a0, a1, ..., an 이라고 하자
* 이 순서에서 몇몇 부분을 조금 늦게 끝난 회의로 배정했을 때
* 배정된 회의의 순서를 b0, b1, ..., bm 이라고 하자
* => 잘 생각해보면 n>=m 일 수밖에 없다
* 조금 늦게 끝난 회의를 배정했을 경우
* 빨리 끝난 순서대로 배정했을 때보다 회의를 적게 할 수 있기 때문이다
* => |---| <= 빨리 끝난 순서
* |--| <= 조금 늦게 끝난 순서도 포함
* |------| / 가능한 해
*
* |---||---| <= 빨리 끝난 순서
* |--| <= 조금 늦게 끝난 순서도 포함
* |---||---| / 가능한 해
*
* Point
* - 시작시간과 종료시간이 같은 회의도 있다
* 때문에, 정렬할 때 종료시간 기준 빠른 순 뿐만 아니라
* 시작시간 기준 빠른 순으로 정렬해야 한다
* + 3 3 => 1 3
* 1 3 3 3
* 3 4 3 4
*/
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
// Set up : Global Variables
struct Meeting { int s, e; };
// Set up : Functions Declaration
bool operator < (Meeting u, Meeting v);
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
int N; cin >> N;
vector<Meeting> M(N);
for (int i=0; i<N; i++)
cin >> M[i].s >> M[i].e;
// Process
sort(M.begin(), M.end());
int ans = 0 /* 지금까지 한 회의의 수 */, et = -1 /* 마지막 회의 종료시간 */;
for (int i=0; i<N; i++) {
/* 현재 회의 M[i] 의 시작시간이 마지막 회의 종료시간보다 같거나 빠르면 */
if (et <= M[i].s) {
ans++; /* 회의 시작 */
et = M[i].e; /* 마지막 회의 종료시간 갱신 */
}
}
// Control : Output
cout << ans << endl;
}
// Helper Functions
bool operator < (Meeting u, Meeting v)
/* Meeting 구조체 정렬을 위한 함수 */
{
/* 종료시간이 빠른 순, 시작시간이 빠른 순으로 정렬 */
return make_pair(u.e, u.s) < make_pair(v.e, v.s);
}