[Baekjoon] 11000_강의실 배정

Gold V

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

---

< 강의실 배정 >

 

문제 풀이 

 

우선순위 큐 a에 [수업 시작 시간, 끝난 시간] 배열로 저장한다. 이때 우선순위는 수업 시작시간이 빠른 순으로, 시작 시간이 같다면 끝나는 시간이 빠른 순으로 정렬한다. 우선순위 큐 a 앞에 들어있는 값부터 뽑아내어 또 다른 우선순위 큐 b에 끝나는 시간만 저장한다. 이때, b 젤 앞에 들어있는 값이 저장하려는 값 보다 작거나 같다면 수업이 끝난 후 다음 수업을 시작할 수 있으므로 b에서 poll 한 후 넣어준다.

 

 

 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 _11000_ { // 강의실 배정

	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> temp = new PriorityQueue<>();

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

 

Main

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

 

- 강의 수(n) 입력

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

- queue 가 빌 때까지 반복

: temp가 비어있다면 그냥 저장

: temp가 비어있지 않고 젤 첫 번째 값이 들어갈 값 보다 작거나 같다면 수업이 끝난 후 다음 수업을 시작할 수 있다는 뜻이므로 poll 후 추가

- 강의실 개수는 temp의 size이므로 temp size 출력

 

---

---