프로그램 명: refrigerator
제한시간: 1 초

우리나라 아이스크림 공장은 여러가지 종류의 아이스크림을 생산하고 있다. 그런데 공장에서생산된 아이스크림의 형태를 그대로 보존하기 위해서는 일정한 온도를 유지해 주어야만 한다. 아이스크림은 종류에 따라 유지해야할 온도의 최소값과 최대값이 정해져 있다. 즉 , A 라는 아이스크림의 유지 온도가 -20 oc ~ 12 oc라면, 냉장고의 온도가 -20 oc에서 -12oc 사이일 때만 아이스크림은 형태가 변형되지 않고 보관될 수 있다. 냉장고의 온도는 고정된 값을 정할 수 있으며 하나의 냉장고에는 여러 종류의 아이스크림이 들어 갈 수 있다.

이 아이스크림 공장에서 생산되는 여러 종류의 아이스크림을 모두 보관 할 수 있도록 냉장고를 준비할 때 사용하는 냉장고의 수가 최소가 되도록 각 냉장고의 온도를 결정하는 프로그램을 작성하라.

예를들어 유지온도가 각각 -20 oc~ -15 oc, -14 oc~ -5 oc , -18 oc~ -13 oc, -5 oc~ -3 oc인 네 개의 아이스크림이 있다고 하면 , -15 oc도 맞추어 놓은 냉장고에 첫 번째와 세 번째 아이스크림을 넣고, -5 oc로 맞추어 놓은 냉장고에 두 번째와 네 번째 아이스크림을 넣으면 두 대의 냉장고로 모든 아이스크림을 보관할 수 있다. 물론 첫 번째 냉장고는 -15 oc대신 -16 oc혹은 -18 oc로 맞추어도 상관없다.

입력 형식

첫 째 줄에 아이스크림 종류의 개수 N( 1 <= N <= 100000 )이 주어지며, 두 번째 줄부터 N+1 번째 줄까지는 각 아이스크림이 그대로 보존되는 최저 보관 온도( -30000 <= Xi <= 30000 ) 와 최고 보관온도 ( -30000 <= Yi <= 30000 ) 가 주어진다. 모든 온도는 정수이다.

출력 형식

필요한 냉장고의 최소 개수 k 를 출력한다.

입출력 예

입력

4
-20 -15
-14 -5
-18 -13
-5 -3

출력

2

출처:
채점 데이터:
[질/답] [제출 현황] [푼 후(2)]
[ 채 점 ] [홈으로]  [뒤 로]