11000번 : 강의실 배정

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

11000번: 강의실 배정

 

문제

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

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

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

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

 

입력

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

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

 

출력

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

 

---

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public 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 arr[][] = new int[n][2];

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

        // sorting
        Arrays.sort(arr, new Comparator<int[]> () {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                } else return o1[0] - o2[0];
            }
        });

        long result = 1;
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 강의 종료 시간 우선순위큐
        int e = arr[0][1]; // 기존 강의 종료 시간
        pq.add(e);
        for (int i = 1; i < n; i++) {
            int ns = arr[i][0]; // 현재 강의 시작 시간
            int ne = arr[i][1]; // 현재 강의 종료 시간

            // 기존 강의실 사용
            if(pq.peek() <= ns) {
                pq.poll();
                pq.add(ne);
            } else { // 새로운 강의실 추가
                result += 1;
                pq.add(ne);
            }
        }

        System.out.println(result);
    }
}

 

해결방법

우선순위 큐를 생각하지 못하여서 초반에 헤맸다. 우선순위큐를 사용해야 하는 문제이다.

일단 입력값들의 시작 시간과 종료 시간을 기준으로 정렬한다.

 

문제를 풀기 위해선 두 가지 경우를 생각해야 한다.

1) 기존 강의실에서 수업하는 경우

2) 새로운 강의실에서 수업하는 경우

 

기존 강의실에서 수업을 하려면 이전 강의들의 종료시간을 알아야 한다. 이를 우선순위 큐로 해결할 수 있다. 

이전 강의들의 종료시간을 우선순위 큐에 넣어놓으면 현재 수업을 기존 강의실에서 할 수 있는지 판단 가능하다.

 

현재 수업 시작 시간이 우선순위 큐에서 뽑은 강의실의 종료시간과 같거나 더 큰 경우 기존 강의실에서 수업을 할 수 있다.

현재 수업 시작 시간이 우선순위 큐에서 뽑은 강의실의 종료시간보다 작은 경우 기존 강의실에서 수업을 할 수 없다. 이때 강의실을 추가하면 된다.