[백준] 19598 : 최소 회의실 개수 (JAVA)

난이도

🥇 5

 

링크

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

19598번: 최소 회의실 개수

---

문제

---

풀이과정

해당 문제는 그리디를 사용하는 문제이다.

 

 예전에 풀었던 비슷한 문제에서는 종료 시점을 기준으로 정렬했기 때문에 이를 토대로 문제를 풀어보려고 했는데 잘 되지 않았다. 그래서 왜 안되지라고 생각하면서 반례를 찾아보니 안되는 반례를 찾았다!

 

만약 4개의 회의가 있고 각각의 시작 시간과 종료 시간이 다음과 같을 때 

0 2
1 4
2 6
4 5

종료 시간을 기준으로 정렬하면 다음과 같다.

0 2
1 4

4 5
2 6

만약 위를 기준으로 회의실을 배정하게 되면 먼저 0 2 시간의 회의가 회의실 1개를 배정받는다.

그 후 1 4는 이전 회의가 끝나는 시간보다 일찍 회의가 시작하기 때문에 회의실을 1개 배정받는다.

다음으로 4 5 회의는 0 2 회의 이후에 회의가 시작하기 때문에 정렬 기준에 따라 해당 회의실에 배정받는다.

마지막으로 2 6 회의는 0 2, 4 5 회의와 1 4 회의 모두에 시간이 맞지 않기 때문에 회의실 1개를 배정받는다.

 

이때 문제가 생기는데 최소한의 회의실을 배정받아야 하기 때문에

이를 따르기 위해선 배정이 다음과 같아야 한다.

0 2 / 2 6

1 4 / 4 5

위의 과정에서는 회의실이 2개만 있으면 되기 때문이다.

 

결국 종료 시간을 기준으로 회의실을 배정하면 안되고 시작 시간을 기준으로 배정해야 하는 것이다!

 

 

1) 우선 회의를 배열에 저장해놓은 후 시작 시간을 기준으로 정렬한다.

2) 이후 처음 회의실에 배정받은 회의의 종료 시간을 우선순위 큐에 저장하고서,

3) 이후 [회의의 시작 시간이 >= 우선순위 큐에 들어간 종료 시간] 이라면

     ➡️ 종료 시간을 우선순위 큐에서 빼고서, 새로운 종료 시간을 넣으면 된다!

      ex) 예를 들어, 0 2가 회의실 배정을 받고서 2가 우선순위 큐에 들어간다

            그 다음 1 4도 회의실을 배정받고 4가 우선순위 큐에 들어간다.

            다음 2 6은 우선순위 큐에 들어있는 2와 같기 때문에 2가 빠지고 6이 들어가
            현재 우선순위 큐에는 4와 6이 들어가 있는 것이다.

            마지막 4 5도 우선순위 큐에 들어가 있는 4와 같기 때문에 4가 빠지고 5가 들어가
            ➡️ 결국 우선순위 큐에는 4와 5가 들어가고 필요한 회의실의 개수는 우선순위 큐의 크기인 2가 된다.

 

 

🚨 우선순위 큐에는 종료 시간만 들어가기 때문에 Integer를 넣어주어야 한다! (객체만 넣을 수 있어서 int X)

🚨 Node 정렬할 때 Comparable - compareTo / Comparator - compare 인거 주의!

---

전체 코드

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

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

        Queue<Integer> pq = new PriorityQueue<>();

        int N = Integer.parseInt(br.readLine());

        Node[] meeting = new Node[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            meeting[i] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(meeting);

        pq.offer(meeting[0].end);

        for (int i = 1; i < N; i++) {
            if (meeting[i].start >= pq.peek()) {
                pq.poll();
            }

            pq.offer(meeting[i].end);
        }

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

class Node implements Comparable<Node>{
    int start, end;

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

    @Override
    public int compareTo(Node next) {
        if (this.start == next.start) {
            return this.end - next.end;
        }
        else {
            return this.start - next.start;
        }
    }
}

 

결과