Informatica Online Judge

  동계 올림픽 녹화 [0916 / 0394]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 26   Total Tried : 156


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[USACO (Brian Dean, 2014)]

Background

농부 경곽이는 동계 올림픽을 매우 좋아한다.

하지만 그는 바쁜 농사일에 동계 올림픽의 모든 종목을 보고 싶어한다.

그래서 경곽이는 모든 올림픽 경기 중계 방송에 대한 편성표를 구했다. 동계 올림픽의 종목은 모두 N개가 방송된다.

그리고 i번째 방송의 시작시각 S_i와 종료시각 E_i을 알 수 있었다.

경곽이는 비디오 레코더를 2대 가지고 있다.

이 1대의 레코더는 한 번에 한 개의 방송을 녹화할 수 있으며, 제대로 녹화하기 위해서는 반드시 시작시각부터 종료시각까지 모두 녹화해야만 한다.

2대의 레코더를 이용해서 최대한 많은 방송을 녹화할 수 있도록 경곽이를 도와주는 프로그램을 작성하시오.

Input

첫 번째 줄에 방송의 수 N이 입력된다.
두 번째 줄부터 N줄에 걸쳐서 각 방송의 시작시각 S와 종료시각 E가 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= N <= 150
0 <= S <= E <= 1,000,000,000

Output

2대의 레코더를 이용해서 녹화할 수 있는 최대의 프로그램 수를 출력하시오.

IO Example

입력
6
0 3
6 7
3 10
1 5
2 8
1 9

출력
4

설명
최대한 4개의 프로그램을 녹화할 수 있다.
레코더 1로는 1, 3번 프로그램을 녹화할 수 있고
레코더 2로 2, 4번 프로그램을 녹화할 수 있다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]