[Algorithm] 정올 1828 냉장고

[ 문제 ]

N개의 화학 물질 C1, C2, …, Cn이 있다.

이들 각각은 보관되어야 할 온도가 각기 다른데, 각 Ci마다 최저 보관 온도 xi와 최고 보관 온도 yi가 정해져 있다. 

즉 Ci는 온도 xi이상, yi이하의 온도에서 보관되어야만 안전하다.

 

이 화학 물질들을 모두 보관하기 위해서는 여러 대의 냉장고가 필요한데 가능하면 적은 수의 냉장고를 사용하고 싶다. 

이를 해결하는 프로그램을 작성하시오.

 

[ 입력형식 ]

• 첫줄에 화학물질의 수 N이 입력된다.
• N의 범위는 1이상 100 이하이다.
• 두 번째 줄부터 N+1줄까지 최저보관온도와 최고보관온도가 입력된다. 
• 보관온도는 -270° ~ 10000°이며, 각 냉장고는 임의의 정해진 온도를 일정하게 유지할 수 있고, 냉장고는 아주 크다고 가정한다.

 

[ 출력형식 ]

• 첫줄에 최소로 필요한 냉장고의 대수를 출력한다.

 

[ 입력 예 ]

4

-15 5

-10 36

10 73

27 44

 

[ 출력 예 ]

2

 

---

 

import java.util.*;
import java.io.*;

public class Main {
	
	static class Chemical implements Comparable<Chemical> {
		int high, low;
		
		public Chemical (int low, int high) {
			super();
			this.low = low;
			this.high = high;
		}
		
		public int compareTo (Chemical o) {
			int value = this.low - o.low;
			if(value != 0)	return value;
			
			return this.high - o.high;
		}
	}
	

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken()); // 화학물질의 수
		Chemical[] chemicals = new Chemical[N];
		
		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			chemicals[n] = new Chemical(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		
		System.out.println(getRefrige(chemicals));
	}
	
	
	static int getRefrige (Chemical[] chemicals){
		int count = 1;
		
		Arrays.sort(chemicals);
		
		int nowLow = chemicals[0].low;
		int nowHigh = chemicals[0].high;
		
		for (int i = 1; i < chemicals.length; i++) {
			if (nowHigh >= chemicals[i].low) { // 겹치는 온도 범위가 있을 경우
				nowLow = chemicals[i].low;
				nowHigh = chemicals[i].high < nowHigh ? chemicals[i].high : nowHigh;
			}
			else { // 겹치는 온도 범위가 없을 경우, 온도 범위를 새로 지정
				count += 1;
				nowLow = chemicals[i].low;
				nowHigh = chemicals[i].high;
			}
		}
		
		return count;
	}
}