백준 11000 강의실 배정

https://www.acmicpc.net/problem/11000

이문제를 풀기전에..

IllegalArithmeticException..

IllegalException 에러가 나온다면.. 이 포스트를 확인하고 풀길바람! (주의할점만 보면됨)

Comparable vs Comparator

메인 아이디어는 다음과같다.

1. 정렬하기
2. PQ에 집어넣어서 가장빠른방이 끝나는지 체크
   3.1 안끝나면 새방
   3.2 끝나면 해당방을 갈아치우기 그리고 가장 빠른방 빼고 교체해주기
3. 현재 방에 넣어주기

근데.. 정렬을 어떻게 하느냐가문제이다..

1. 먼저 끝나는순으로 정렬을하면 다음과같이 문제가됨

1 3
2 5
7 8
9 10
4 12

1 3 | 7 8 |
2 5 | 9 10 |
4 12|

이렇게 3개를 사용하게됨

하지만 올바르게 배열했을때에는

1 3 | 4 12 |
2 5 | 7 8 | 9 10 |
이렇게 2개를 사용하게된다.

그래서 시작순으로 배열을 하고.. 끝나는순으로 PQ에 넣어주고 처리가필요하다.

코드는 다음과같다.

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

class rooms implements Comparable<rooms>{
	long s;
	long e;
	
	public rooms (long s,long e) {
		this.s= s;
		this.e=e;
	}
	
	public int compareTo(rooms o){
		if(o.s<s) return 1;
		else if(o.s==s) {
			if(o.e<e) return 1;
            else if(o.e==e){
                return 0;
            }
            else {
                return -1; 
            }    
		}
        else {
		return -1;
        }
	}
}

public class 강의실배정 {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine());
		
		PriorityQueue<Long> pq = new PriorityQueue<>();
		ArrayList<rooms> rlist = new ArrayList<>();
		StringTokenizer st;
		for(int i=0;i<tc;i++) {
			st = new StringTokenizer(br.readLine());
			long s = Long.parseLong(st.nextToken());
			long e = Long.parseLong(st.nextToken());
			
			rlist.add(new rooms(s,e));

		}
		Collections.sort(rlist);
		for(rooms cur : rlist) {
			if(!pq.isEmpty()) {
				if(pq.peek()<=cur.s) {
					pq.poll();
				}
			}
			pq.add(cur.e);
		}
		
		
		int answer  = pq.size();
		System.out.println(answer);
	}

}

ㅎㅎㅎ.... 많이틀렷지만..ㅠㅠ.. 얼른 골드4로 넘어가자..