백준 최소 회의실 개수(우선순위 큐, 그리디)★★

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

19598번: 최소 회의실 개수

매우 어려운 문제였지만 원리를 이해한다면 쉽다.

 

> 접근방법

우리는 회의실을 가장 적게 쓰고 싶어한다.

주어지는 입력은 무작위로 들어올텐데 문제를 읽어보면

진행되는 회의의 종료시간과 다음 회의 시작시간의 상관관계가 가장 중요하다는 것은 알 수 있다.

즉, 회의 데이터들의 입력을 받고 시작시간 기준으로 정렬해줄 필요가 있다.

why?)

그래야 순차적으로 회의실을 늘릴지말지 판별할 수 있지 않은가?

 

자, 우리는 이제 회의 데이터를 읽어나가면서 지금 진행되는 회의보다 시작시간이 먼저인 회의는 절 때 나오지 않는다(시작시간에 대해 정렬 해줘서)

for(int[] time:meetings) {
    if (pq.peek() > time[0]) //min-heap이 시작시간보다 크면 회의실 추가
        cnt++;
    else
        pq.poll(); //회의실을 이어서 쓸 수 있다는 거니까 이전의 정보 삭제
    pq.add(time[1]);
}

우리는 회의가 진행되는 정보를 어떤 자료구조에 넣어서 관리를 하려고 하는데 이 문제에서 중요한 부분은

진행되는 여러가지 회의들 중 제일 빨리 끝나는 회의시간을 지속적으로 알아야할 필요가 있다

why?)

최소의 회의실을 사용해야하는데 먼저 끝나는 회의실에 대한 정보를 가지고 활용해야한다.

예를 들어 10에 끝나는 회의가 있는데 다음 회의가 10이상인 시간에 시작된다고 하면 회의실을 늘릴 필요가없다. 이러한 판단은 어떻게 할 수 있겠는가?

=> 우선순위큐를 이용하여 값을 넣으면 최소값이 자동으로 정렬되고 가장 빨리 끝나는 시간을 앞에둬서 pq.peek()로 접근 가능하여 활용하기 편리하기 때문에 Priority Queue를 사용한 것

 

package practice;

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


public class Main_19598 {

	public static void main(String[] args) throws  IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[][] meetings = new int[n][2];
		int cnt = 0;
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		for (int i = 0; i < n; i++) {
			String[] input = br.readLine().split(" ");
			for (int j = 0; j < 2; j++) {
				meetings[i][0] = Integer.parseInt(input[0]);
				meetings[i][1] = Integer.parseInt(input[1]);
			}
		}
	
		Arrays.sort(meetings, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});
		
		
		pq.add(Integer.MAX_VALUE);
		
		for(int[] time:meetings) {
			if (pq.peek() > time[0]) //min-heap이 시작시간보다 크면 회의실 추가
				cnt++;
			else
				pq.poll(); //회의실을 이어서 쓸 수 있다는 거니까 이전의 정보 삭제
			pq.add(time[1]);
		}
		
		
		
		
		System.out.println(cnt);
		
		
	}

}