[백준] 11000번 - 강의실 배정 (java)

Baekjoon 11000 - 강의실 배정 (클릭 시 이동)

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	14977	4452	3231	29.365%

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

풀이

1. 시작시간의 오름차순으로 우선순위를 갖는 큐(waitPQ)를 만들고 모든 입력값의 쌍을 집어넣는다.
2. 종료시간의 오름차순으로 우선순위를 갖는 큐(ingPQ)를 만든다.
3. waitPQ에서 하나씩 빼보았을 때 start가 ingPQ의 맨 첫 요소의 종료시간과 비교해본다.
4. start가 ingPQ에서 가장 먼저 종료되는 요소의 시간보다 크거나 같다면 그러한 요소를 찾아 모두 뺀다.
5. 그렇지 않다면 ingPQ에 집어넣고 max를 업데이트 해 준다.

최종 소스코드

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

public class BJ_G5_11000_강의실_배정 {

    static int N;
    static StringTokenizer st;

    static class Time{
        int start, end;

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

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

        // Lambda식을 이용한 PQ 설정.
        // start의 오름차순
        PriorityQueue<Time> waitPQ = new PriorityQueue<>((o1,o2)-> {return o1.start - o2.start;});
        //end의 오름차순
        PriorityQueue<Time> ingPQ = new PriorityQueue<>((o1,o2)-> {return o1.end - o2.end;});

        N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N ; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            waitPQ.offer(new Time(start,end));
        }
        int max = -1;
        while(!waitPQ.isEmpty()) {
            Time temp = waitPQ.poll();

            if(ingPQ.isEmpty()) {    // ingPQ가 비어 있다면 peek을 할 수 없으므로.
                ingPQ.add(temp);
                max = Math.max(max, 1);
            }else {
                // start보다 작은 end를 모두 뺀다.
                while(!ingPQ.isEmpty() && ingPQ.peek().end <= temp.start){
                    ingPQ.poll();
                }
                ingPQ.offer(temp);        // 넣는다.
                max = Math.max(max, ingPQ.size());    // 정답을 업데이트 한다.
            }
        }
        System.out.println(max);

    }
}