[Algorithm] 99클럽 코테 스터디 20일차 TIL | 백준_최소 회의실 개수(19598번)

📝문제

 

💡풀이

1. 시작한 시간을 기준으로 오름차순 정렬한다. 

2. 첫 시간은 어차피 1개의 회의실을 써야하므로 room = 1로 시작

3. 시작한 시간의 끝나는 시간을 우선순위 큐에 넣음

4. 큐에 들어간 첫번째 값(종료시간)과 현재 시작 시간을 비교해서 시작 시간이 종료 시간보다 작을 때 회의실을 같이 쓸 수 없다. -> room++

5. 시작 시간이 종료 시간보다 크거나 같을 때 회의실을 같이 쓸 수 있다 -> 큐에서 종료시간을 꺼내줌

import java.util.*;
import java.io.*;
class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] time = new int[N][2];

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

        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            time[i][0] = Integer.parseInt(st.nextToken());
            time[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(time, Comparator.comparingInt(a->a[0]));
        pq.add(time[0][1]);

        int room = 1;
        for(int i = 1; i < N; i++){
            if(time[i][0]<pq.peek()){//시작 시간이 종료 시간보다 작을 때
                //회의실을 같이 쓸 수 없음
                room++;
            }else{//시작 시간이 종료 시간보다 크거나 같을 때
                //회의실을 같이 쓸 수 있음
                pq.poll();
            }
            pq.add(time[i][1]);
        }

        System.out.println(room);
    }
}

 

🤔Review

간단해보이지만 어려웠다. 우선순위 큐를 사용할 생각을 못한 게 아쉽다.