정올- 1828.냉장고

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=99&sfl=wr_hit&stx=1828 

JUNGOL

문제

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

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

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

 

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

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

 

입력형식

첫줄에 화학물질의 수 N이 입력된다. N의 범위는 1이상 100 이하이다. 

두 번째 줄부터 N+1줄까지 최저보관온도와 최고보관온도가 입력된다. 

보관온도는 -270° ~ 10000°이며, 각 냉장고는 임의의 정해진 온도를 일정하게 유지할 수 있고, 냉장고는 아주 크다고 가정한다.

 

출력형식

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

 

 

package a0817;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_Jo_냉장고_서울_12반_이서영 {
	
	static int n;
	static Chem[] arr;
	static StringTokenizer st;
	
	static class Chem implements Comparable<Chem>{ //comparable인터페이스 적용
		int low;
		int high;
		Chem(int low, int high){
			this.low = low;
			this.high = high;
		}
		
		@Override
		public int compareTo(Chem o) {
			
			if(this.high==o.high) {
				return Integer.compare(this.low, o.low); //high가 같을 땐 낮은 온도 기준으로 오름차순 정렬 
			}
			
			return Integer.compare(this.high, o.high); //high 기준으로 오름차순
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr = new Chem[n];
		for(int i=0; i<n; i++) {
			
			st = new StringTokenizer(br.readLine());
			arr[i] = new Chem(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			
		}
		
		Arrays.sort(arr); // sort를 시켜준다
		int ref = 0; //냉장고의 개수 
		for(int i=0; i<arr.length;i++) {
			
			Chem ch = arr[i]; 
			//int idx = i;
			int idx = i;
			ref++; 
			i++;
			while(i<arr.length) {
				if(arr[i].low>=arr[idx].high) { // idx번쨰의 high보다 그 뒤에 있는 용액의 low점이 더크면 while문 빠져나오기
					break;
				}
				i++; 
			}
			i--;
			
			
		}
		System.out.println(ref);
		
		
	}
	
}