[백준 11000 JAVA] 강의실 배정

 

그리디 알고리즘과 우선순위 큐를 사용하는 문제이다.

 

입력을 받은 후 시작시간 순으로 정렬을 한다. (시작시간이 같으면 끝나는 시간이 빠른 순으로)

 

순서대로 우선순위 큐에 끝나는 시간을 넣어준다.

 

만약 다음 수업의 시작이 우선순위 큐 맨위에있는 끝나는 시간보다 늦다면 하나의 강의실에 배치 가능한것

이때는 우선순위 큐 맨 위에있는 수업을 빼고 다음 수업의 끝나는 시간을 넣어준다.( 큐에서 빠진다는 것은 한 강의실에 배치 가능하다는 것)

 

=> 새로 수업을 넣으면 재정렬이되어 끝나는시간 순서대로 배치가 된다.

=> 앞에 수업이 큐에서 빠지면 다음으로 끝나는 시간이 빠른 수업이 맨 위로 올라온다.

 

계속 진행하다 종료되었을 때, 큐에 남아있는 수업들이 강의실에 함께 배치하지 못하는 수업이다.

 

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

class Timetable {
    int start;
    int end;

    Timetable(int start, int end) {
        this.start = start;
        this.end = end;

    }
}

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

        Timetable[] timetable = new Timetable[N];

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            timetable[i] = new Timetable(start, end);
        }
        Arrays.sort(timetable, (t1,t2) -> t1.start == t2.start ? t1.end-t2.end : t1.start - t2.start);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(timetable[0].end);

        for(int i=1; i<N; i++){
            if (pq.peek() <= timetable[i].start){
                pq.poll();
            }
            pq.offer(timetable[i].end);
        }
        System.out.println(pq.size());
    }
}