BOJ - 11000 강의실 배정

11000 강의실 배정 : https://www.acmicpc.net/problem/11000

---

Problem

---

Solve

주어진 수업시간의 시작시간 기준 오름차순으로, 동일하다면 끝시간 오름차순으로 정렬한다.

PriorityQueue< Integer >에 수업을 시작할수 있는 시간을 넣어준다. PQ의 크기가 강의실의 개수가 된다.
PQ를 사용함으로써 현재 수업 시작 시간이 사용할수 있는 시간과 가장 빨리 사용할수 있는 강의실의 시간을 비교하여 기존 강의실을 사용할수 있는지, 새로운 강의실을 사용해야하는지 여부를 판단할수 있다.

수업시간이 정렬된 배열을 돌면서 PQ에 있는 수업중 가장 빠른 시간이 현재 수업시작시간보다 작거나 같다면 수업을 연속으로 할 수 있다.
PQ에 있는 가장 빠른 시간이 현재 수업시작시간보다 크다면 현재 수업을 PQ에 추가한다.(강의실을 추가한다)

첫번째 풀이로 수업 끝시간을 기준으로 오름차순으로 정렬했다가 틀렸는데 반례가 있었다.
N이 6이고
1 3
2 5
7 8
9 10
7 11
4 12 일때

강의실 1 : (1,3),(7,8),
강의실 2 : (2,5), (9,10)
강의실 3 : (7,11)
강의실 4 : (4,12) 가 되므로 총 4개의 강의실을 사용해야한다.

하지만 최소 강의실은

강의실 1 : (1,3), (4,12)
강의실 2 : (2,5), (7,8), (9,10)
강의실 3 : (7,11) 가 되므로 3개의 강의실을 사용할수 있다.

---

Code

public class 강의실배정 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		int[][] T = new int[N][2];

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int s = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());

			//0번 index : 수업 시작시간, 1번 index : 수업 끝 시간
			T[i] = new int[] {s, t};
		}

		//시작시간 오름차순, 같다면 끝시간 오름차순
		Arrays.sort(T, (o1, o2)->{
			if(o1[0]==o2[0]){
				return o1[1]-o2[1];
			}else{
				return o1[0]-o2[0];
			}
		});

		//수업시작할수 있는 시간으로 오름차순
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		pq.offer(T[0][1]);

		for(int i=1;i<N;i++){
        	//pq에서 가장 빠른 시간이 현재 수업시간의 시작시간보다 빠르다면 연속으로 수업을 진행할수있다.
            //pq에서 시간을 빼고 현재 수업의 끝시간을 넣어서 pq에 수업시작할수 있는 시간을 갱신하고 pq의 크기(강의실 개수)를 유지한다
			if(pq.peek() <= T[i][0]){
				pq.poll();
			}
			pq.offer(T[i][1]);
		}

		bw.write(String.valueOf(pq.size()));
		bw.flush();
		bw.close();
	}
}

---

Result

---

Reference

https://steady-coding.tistory.com/253