[boj] 백준 gold5 11000 강의실 배정 (Java) - 그리디

[문제]

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

[풀이]

처음에는 앞서 풀었던 회의실 배정 문제와 같이 한 강의실에 최대한의 인원을 넣고 강의실에 배정받았다는 bool 변수를 둔 후 while문을 돌며 관리하려고 했다. 그런데 N이 커서 시간이 너무 커진다..

 

풀이 시나리오는 다음과 같다.

1. 강의 시작 시간 오름차순으로 정렬해준다.

2. 강의 종료 시간을 저장하는 우선순위 큐를 선언한다. 우선순위 큐는 기본 오름차순으로 데이터를 저장한다.

3. 회의실 배정 문제와 같이 현재 강의의 종료시간보다 다음 강의의 시작 시간이 같거나 늦으면 같은 강의실에 배정 가능하다. 이 경우 우선순위 큐를 poll() 한 후 새로 배정받은 강의의 종료 시간을 offer 해준다.

4. 만약 같은 강의실에 배정 불가능하다면 새로운 강의실을 배정해야 한다. 해당 강의의 종료 시간을 우선순위 큐에 offer해주면 새로운 강의실에 배정받은 것이다.

5. 다시 다음 강의에 대해 비교가 이루어질 때 우선순위 큐에 의해 종료시간이 가장 빠른 강의와 비교가 될 것이다. 어차피 그 강의보다 시작 시간이 앞서있어서 강의실 배정이 불가능하다면 다른 강의실에도 배정 못받는 것이 확실시 되는 것.

 

[코드]

 

package 그리디;

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

public class boj_11000_강의실배정 {
    static int n;
    static int[][] times;
    static PriorityQueue<Integer> pq;

    public static void main(String[] args) throws Exception{
        //최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. -> 한 강의실에 최대한 많이 배정

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        times = new int[n][n];

        pq = new PriorityQueue<>();
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            times[i][0] = Integer.parseInt(st.nextToken());
            times[i][1] = Integer.parseInt(st.nextToken()); 
        }

        Arrays.sort(times, (o1, o2) -> (o1[0]-o2[0])); //시작 시간 오름차순 정렬

        int end = times[0][1];
        pq.offer(end);

        for(int i=1; i<n; i++){
            if(pq.peek() <= times[i][0]){ //종료시간 보다 시작 시간이 더 늦으면 배정 가능
                pq.poll();
                pq.offer(times[i][1]);
            }
            else{
                //새로운 회의실에 배정
                pq.offer(times[i][1]);
            }
        }
        
        System.out.println(pq.size());

    }
    
}