[Baekjoon] 19598_최소 회의실 개수

Gold V

문제(출처: https://www.acmicpc.net/problem/19598)

---

< 최소 회의실 개수 >

 

문제 풀이 

 

우선순위 큐 2개를 사용해서 문제를 해결했다.

우선순위 큐 하나에는 [회의 시작 시간, 회의 끝나는 시간] 배열을 저장해서 우선순위를 회의 시작시간이 빠른 순으로, 시작 시간이 같다면 끝나는 시간이 빠른 순으로 정렬했다.

다른 우선순위 큐에는 회의 끝나는 시간을 저장한다. 이때, 이 우선순위 큐 젤 앞에 있는 값이 새로 들어오는 값 보다 작거나 같다면 회의가 끝난 후 다음 회의를 시작할 수 있는 것이므로 poll해준 후 넣어준다.

 

* 11000번 강의실 배정 문제와 거의 똑같은 문제였다.

https://melody-coding.tistory.com/367

[Baekjoon] 11000_강의실 배정

 

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _19598_ { // 최소 회의실 개수

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		PriorityQueue<int[]> queue = new PriorityQueue<>(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];
			}
		});

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			queue.add(new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) });
		}

		PriorityQueue<Integer> room = new PriorityQueue<>();
		room.add(queue.poll()[1]);

		while (!queue.isEmpty()) {
			int time[] = queue.poll();
			if (room.peek() <= time[0]) {
				room.poll();
			}
			room.add(time[1]);
		}
		System.out.println(room.size());
	}
}

 

Main

변수)
n : 회의 수
queue: 우선순위 큐 [회의 시작 시간, 회의 끝난 시간]
room: 우선순위 큐 [회의 끝난 시간] 

 

- 회의 수(n) 입력

- 회의 수만큼 입력받아 우선순위 큐 queue에 저장

- room 우선순위 큐에 queue 값을 뽑아 먼저 회의실 하나 저장

- queue 가 빌 때까지 반복

: room 우선순위 큐의 젤 첫 번째 값이 들어갈 값 보다 작거나 같다면 회의가 끝난 후 다음 회의를 시작할 수 있다는 뜻이므로 poll 후 추가

- 회의실 개수는 room의 size이므로 room size 출력

 

---

---