백준[19598] 최소 회의실 개수

• 문제: https://www.acmicpc.net/problem/19598
• 분류: 그리디, 정렬, 우선순위큐
• 난이도: G5
• 소요시간: 15m
• 자아성찰:
  • 처음에는 남은 회의 중 종료 시간이 빠른 순으로 배정된 회의실중 종료시간이 제일 빠른 회의실을 배정하면 되겠다라고 생각했다.
  • 스스로 테스트케이스를 생각해보면서, 다음 같은 상황에서 답이 맞지 않을 것 같았다.
    • 현재 배정된 회의실 중 종료시간은 30, 40
    • 남은 회의는 50-60 / 30-70
    • 50-60 회의가 종료시간 30 회의실 배정
    • 30-70 회의실은 종료시간 40 회의실 배정이 불가하므로 회의실 +1
    • 30-70 회의가 30 회의실을 먼저 배정받고, 50-60 회의가 40 회의실을 배정받으면 추가로 회의실 배정 필요없음
  • 시작시간이 빠른 순 / 시작시간이 같을 경우 종료시간 빠른 순으로 회의를 정렬하면 빨리 시작해야 하는 회의가 최대한 종료시간이 빠른 회의실을 먼저 배정받을 수 있겠다라고 생각했다.

---

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

public class B_19598 {

    static int N, result;
    // 회의 시작 빠른 순 PQ
    static PriorityQueue<Meeting> meet = new PriorityQueue<>();
    // 회의실 종료시간 빠른 순 PQ
    static PriorityQueue<Integer> room = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            meet.add(new Meeting(start, end));
        }
        while (!meet.isEmpty()) {
            Meeting cur = meet.poll();
            // 회의실 새로 배정 (첫 회의 or 비어있는 회의실 없는 경우)
            if (room.isEmpty() || cur.start < room.peek()) {
                result++;
                room.add(cur.end);
            } else {
                // 기존 회의실 사용
                room.poll();
                room.add(cur.end);
            }
        }
        System.out.println(result);
    }

    static class Meeting implements Comparable<Meeting> {
        private final int start;
        private final int end;

        public Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }

        // 시작시간 빠른 순 / 같을 경우 종료시간 빠른 순
        @Override
        public int compareTo(Meeting obj) {
            if (this.start == obj.start) {
                return obj.end - this.end;
            }
            return this.start - obj.start;
        }
    }
}