19598 최소 회의실 개수

지난번 풀었던 문제와 동일했다.

N개의 회의를 마칠 수 있는 최소 회의실의 개수를 찾아야 하는 문제이고, 우선순위 큐를 사용해서 해결했다.

 

M개의 회의실의 타임라인이 있다고 생각해 보자.

두 가지의 경우가 나온다.

1. 회의실이 비었다면(진행 중인 회의가 끝났다면) 다음 회의를 이어서 배정.

2. 빈 회의실이 없다면, 새로운 회의실에 배정

 

우선순위 큐에 있는 요소들을 각 회의실의 타임라인이라고 생각하면 될 것 같다.

우선순위 큐는 회의 종료시간을 오름차순으로 설정했기 때문에, 가장 먼저 끝나는 회의가 우선적으로 출력된다.

 

회의실의 타임라인을 우선순위 큐라고 생각하면 다음과 같이 될 것이다.

1. 우선순위 큐의 앞에 있는 회의가 끝났다면, 제거하고 다음 회의를 큐에 추가한다.

   -> 같은 회의실을 이어서 사용

2. 우선순위 큐의 앞에 있는 회의가 끝나지 않았다면, 다음회의를 큐에 추가한다.

   -> 새로운 회의실 사용

 

이 과정을 반복하고 모든 회의를 할당하고 나면, 우선순위 큐에는 각 회의실의 마지막 회의가 남아있을 것이다.

즉, 우선순위 큐의 크기가 회의실의 개수이다.

 

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        Meeting[] meetings = new Meeting[N];
        for (int i = 0; i < N; i++) {
            String[] split = br.readLine().split(" ");
            meetings[i] = new Meeting(Integer.parseInt(split[0]), Integer.parseInt(split[1]));
        }

        Arrays.sort(meetings);

        Queue<Integer> pq = new PriorityQueue<>();  // 오름차순 우선순위 큐
        pq.add(meetings[0].end);
        for (int i = 1; i < N; i++) {
            Meeting curremtMeeting = meetings[i];

            if (pq.peek() <= curremtMeeting.start) {
                pq.poll();
                pq.add(curremtMeeting.end);
            }
            else {
                pq.add(curremtMeeting.end);
            }
        }

        System.out.println(pq.size());
    }

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

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

        @Override
        public int compareTo(Meeting m) {
            return Integer.compare(this.start, m.start);
        }
    }
}