백준 19598번: 최소 회의실 개수

문제 설명

• https://www.acmicpc.net/problem/19598
• 주어진 회의를 진행하기 위해 필요한 최소 회의실 개수를 구하는 문제입니다.

접근법

• 회의실 배정 문제와 유사하지만 차이가 존재합니다.
  개인적으로 [0 50], [20 100], [50, 60], [60, 120]형태를 고려하는 게 문제의 핵심이라고 생각합니다. 이 예제는 단순히 시작시간으로 정렬하거나 종료시간으로 정렬해서 풀기 어려운상황입니다. 그림으로 살펴보면 다음과 같습니다.
  
  • 위 예제는 A - D - B가 연속적으로 하나의 회의실에서 진행이 가능하기 때문에 총 2개의 회의실이 필요한 상황입니다.
  • 하지만 이를 시작시간 또는 종료시간으로 단순 정렬한 뒤 이전의 값과 현재의 값을 비교하면 이러한 상황을 고려할 수 없습니다.
  • 시작시간을 기준으로 정렬하고 D를 조사할 때 pq의 이전값인 C만 검사하는 게 아니라 A까지 함께 고려해 줘야 한다는 얘기입니다.
• 2개의 pq를 사용해서 문제를 풀었습니다. 하나는 회의의 시작시간 기준으로 값을 꺼내기 위한 pq(MeetingInfo), 다른 하나는 각 회의실에서 진행중인 회의의 종료시간을 나타내는 pq(EndTimeOfOccupiedRoom)입니다.
  시작시간을 기준으로 어떤 회의 정보(now)를 꺼냈을 때, 앞선 회의들 중 가장 일찍 끝나는 회의(EndTimeOfOccupiedRoom.peek())가 이미 끝나 있어서 해당 회의실에서 회의를 진행할 수 있으면 회의실을 늘리지 않습니다.

정답

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

public class Main {
	static TreeSet<String> answer = new TreeSet<String>();
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
        
		PriorityQueue<int[]> MeetingInfo = new PriorityQueue<int[]>((a,b) -> a[0]-b[0]);
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			MeetingInfo.add(new int[] {a,b});			
		}
		
		PriorityQueue<Integer> EndTimeOfOccupiedRoom = new PriorityQueue<Integer>((a,b)->a-b);
		int[] start = MeetingInfo.poll();
		EndTimeOfOccupiedRoom.add(start[1]);
        
		while(!MeetingInfo.isEmpty()) {
			int[] nowConference = MeetingInfo.poll();
			int FastestEndTimeOfOccupiedRoom = EndTimeOfOccupiedRoom.peek();
            
            // 가장 일찍 끝나기로 예정된 회의실이 끝나서 nowConferece가 해당 회의실에서 회의를 진행할 수 있으면
			if(FastestEndTimeOfOccupiedRoom <= nowConference[0]) {
				EndTimeOfOccupiedRoom.poll();
			}
            
			EndTimeOfOccupiedRoom.add(nowConference[1]);
		}
		System.out.println(EndTimeOfOccupiedRoom.size());

	}

}