[백준] 11000번 강의실 배정(java)

문제 Gold5

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

11000번: 강의실 배정

---

풀이

우선순위 큐(PriorityQueue) 활용

우선순위 큐란? 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조

 

문제에서는 강의가 가장 일찍 끝나는 강의실이 우선순위로 배정되어야 함(PriorityQueue Default)

 

강의의 start와 end를 int[]로 입력받아 저장.끝나는 시간을 기준으로 오름차 순 정렬.첫 번째 원소의 endTime을 큐에 먼저 넣고, 반복문 수행현재 가장 일찍 끝나는 강의 시간(time.peek())이 비교하는 강의의 시작 시간(lectures[i][0]) 보다 크다면 강의 진행 가능.이 경우, 해당 강의실의 endTime을 재 설정 해주어야 하므로 poll한 후 다시 offer 수행최종적으로 결과값인 큐의 사이즈를 출력

 

코드

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

public class Main{
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] lectures = new int[N][2];
		for(int i =0 ; i< N ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			lectures[i][0] = Integer.parseInt(st.nextToken());
			lectures[i][1] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(lectures, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0] == o2[0]) return o1[1] - o2[1];
				return o1[0] - o2[0];
			}
		});
		PriorityQueue<Integer> time = new PriorityQueue<>();
		time.offer(lectures[0][1]);
		for(int i = 1; i<lectures.length ; i++) {
			if(time.peek() <= lectures[i][0]) time.poll();
			time.offer(lectures[i][1]);
		}
		System.out.println(time.size());
	}
}