1374번 : 강의실

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

1374번: 강의실

 

문제

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다.

 

출력

첫째 줄에 필요한 최소 강의실 개수를 출력한다.

 

---

소스코드

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

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());
        StringTokenizer st;

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

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

        int result = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            int s = arr[i][0];
            int e = arr[i][1];
            if(!pq.isEmpty()) {
                if(pq.peek()>s) result += 1;
                else pq.poll();
            } else result += 1;
            pq.add(e);
        }

        System.out.println(result);
    }
}

 

해결방법

강의 시작시간 순으로 그림을 그려보면 위 사진과 같이 그려진다.

결국, 강의실 수를 찾으려면 시작 시간과 종료 시간을 비교해야 한다.

 

시작 시간과 종료 시간을 단순하게 순차적으로 비교한다면 시간초과가 날 것 이다.

고로 현재 강의의 시작 시간 전에 종료된 강의가 있는 지 O(1)만에 찾아야 한다.  

우선순위 큐를 떠올릴 수 있다. 삽입은 O(logN) 우선순위가 높은 요소 조회는 O(1)이기 때문이다.

 

시작 시간순으로 돌면서 큐에 종료된 강의실이 있고 종료 시각이 현재 강의의 시작 시간보다 빠르다면 해당 강의실을 이용하고, 아니라면 새로운 강의실을 추가하면 된다.