[백준] 회의실 배정 JAVA

반응형

728x90

[백준] 회의실 배정 - SILVER I 1931번

---

접근

• 우선순위 큐
• 그리디

---

풀이

주어지는 회의를 적절히 배치하여 회의실에서 가장 많이 회의를 진행할 수 있는 경우가 몇 개인가를 구하는 문제이다. 회의는 한 번 시작하면 중단될 수 없는 비선점의 조건이고 회의가 끝나고 시작하는 시점이 같아도 허용된다. 우선순위 큐를 사용한다면 간단하게 구할 수 있는 문제이다. 예전에 올렸던 디스크 컨트롤러와도 비슷한 결의 문제인데 그것보다 훨씬 더 간단하다.

PriorityQueue<int[]> que = new PriorityQueue<>((a, b) -> {
            if (a[1] != b[1]) {
                return a[1] - b[1];
            } else {
                return a[0] - b[0];
            }
        });

회의를 담을 우선순위 큐로 회의의 시작시간과 종료시간이 담긴 배열을 담는다. 정렬 기준으로는 회의 종료 시간이 빠른순으로 정렬을 하고 같을 경우 시작 시간이 짧은 것이 우선이 된다.

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

        for (int i = 0; i < N; i++) {
            String[] line = br.readLine().split(" ");
            int start = Integer.parseInt(line[0]);
            int end = Integer.parseInt(line[1]);

            que.offer(new int[]{start, end});
        }

입력받는 회의를 큐에 넣어주는 과정이다.

	int current = 0;
        int result = 0;

        while (!que.isEmpty()) {
            int[] conference = que.poll();
            int start = conference[0];
            int end = conference[1];

            if (current <= start) {
                result++;
                current = end;
            }
        }

진행할 회의를 결정하는 과정으로 현재 시간을 체크할 변수와 회의 개수를 담을 결과 변수를 선언한다. 큐를 우선순위를 기준으로 뽑아내면서 현재 시간과 회의 시작 시간을 비교해 회의가 시작이 가능하다면 회의를 진행하고 현재 시간을 회의가 끝나는 시간으로 바꿔준다.

---

전체 코드

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

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

        PriorityQueue<int[]> que = new PriorityQueue<>((a, b) -> {
            if (a[1] != b[1]) {
                return a[1] - b[1];
            } else {
                return a[0] - b[0];
            }
        });

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

        for (int i = 0; i < N; i++) {
            String[] line = br.readLine().split(" ");
            int start = Integer.parseInt(line[0]);
            int end = Integer.parseInt(line[1]);

            que.offer(new int[]{start, end});
        }

        int current = 0;
        int result = 0;

        while (!que.isEmpty()) {
            int[] conference = que.poll();
            int start = conference[0];
            int end = conference[1];

            if (current <= start) {
                result++;
                current = end;
            }
        }

        System.out.println(result);
        br.close();
    }
}