[백준 | Java] 1931 회의실 배정

내 풀이

이 문제처럼 시간표를 최대한 많이 배정하거나 선택하는 문제를 활동 선택 문제라고 하며 대표적으로 그리디 알고리즘을 사용해 풀 수 있다.

💡 활동 선택 문제
한 사람이 하나의 활동에 대해서만 작업할 수 있을 때 최대한 많은 활동을 할 수 있는 수를 선택하는 문제
👉 한 사람이 하나의 활동에 대해서만 작업할 수 있음
👉 하나의 활동을 완료하기 전까지는 다른 활동을 선택할 수 없음

회의가 빨리 끝날수록 남은 시간에 더 많은 회의를 잡을 수 있으므로, 회의가 끝나는 시점이 빠른 회의부터 오름차순 정렬을 해 순서대로 회의를 시작시킨다.
이 때, 앞의 회의가 끝나는 시간보다 뒷 회의가 시작하는 시간이 더 앞이라면, 그 뒷 회의는 건너뛰고 회의 시간이 겹치지 않는 그 다응 회의를 시작한다.
이를 구현한 풀이과정을 다음과 같다.

1. 내부 정적 클래스로 미팅 클래스를 생성
2. 우선순위큐로 회의가 시작되는 시간을 기준으로 오름차순 정렬
   👉 만약 두 회의의 종료 시간이 같다면, 시작 시간을 기준으로 오름차순 정렬
3. 우선순위 큐가 빌 때 까지
   뒷 회의를 우선순위 큐에서 poll해와서 회의 시간이 겹치지 않는다면 회의 횟수+1

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

public class Main {
    static int N;
    static int result = 0;
    static Queue<meeting> queue;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        queue = new PriorityQueue<>(N, (meeting m1, meeting m2) ->
                m1.end == m2.end ? m1.start - m2.start : m1.end - m2.end);

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            queue.add(new meeting(s, e));
        }
        min();
        System.out.println(result);
    }
    static void min() {
        int end = 0;
        while (!queue.isEmpty()) {
            meeting m = queue.poll();
            if (m.start >= end) {
                end = m.end;
                result++;
            }
        }
    }
    static class meeting {
        int start, end;
        meeting (int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}