냉장고 문제

 프로그램 명: refrigerator

우리나라 아이스크림 공장은 여러가지 종류의 아이스크림을 생산하고 있다. 

그런데 공장에서생산된 아이스크림의 형태를 그대로 보존하기 위해서는 

일정한 온도를 유지해 주어야만 한다. 아이스크림은 종류에 따라 유지해야할 

온도의 최소값과 최대값이 정해져 있다. 즉 , 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

이문제 일차원배열로 sort함수를 쓰고 하나 sort없이 정렬로 하나 

총두개의 방법으로 풀어주세요.. 부탁드립니당

[1] 낮은 온도를 중심으로 정렬을 합니다.

-20 -15   처음에 나오는 온도범위중에서 가장 낮은 온도를 -20 가장 높은 온도를 -15로 합니다.

-18 -13    가장낮은 온도는 -18로 올라가고 가장 높은 온도는 -15로 유지 (항상 내려갈 수만 있습)

-14 -5     가장낮은 온도가 -18과 -15사이에 있지 않습니다. 해결이 안됩니다.

               다시 -14 -5로 시작합니다. (재출발)

-5  -3       -5 -5가 되어서 해결이 되었습니다.

위와 같이 해결을 하면 되겠습니다.

     min1 max1

     min2 max2

정렬을 해 두었기 때문에 min1<=mini2 입니다. 

위와 같이 내려 갈때 min2<=max1 라면 계속 현재 온도범위에서 해결가능합니다.

    min2  maxx  여기서 maxx는 max1, max2 중에서 낮은 값이 됩니다.

이렇게 새로 바뀐 값을 가지고 다시 다음 온도 범위를 가지고 따져봅니다.