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

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)

출력

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

예제

3
1 3
2 4
3 5

 

2

 

 

풀이 1

정렬을 이용하지 않고 간단하게 강의가 시작할 때와, 끝날 때를 나눠서 받은 후 PriorityQueue를 이용해서 필요한 강의실 수의 max를 구했습니다.

강의의 시간인 time과 강의가 시작 시간인지 끝 시간인지를 나타내 주는 inout 변수를 가진 Class라는 클래스를 만들었습니다. (클래스 이름을 Class로 설정하니 조금 헷갈리는 점 양해 부탁드려요 ^^..)

시작 시간인 s가 들어온다면 new Class ( s , 1 )을 저장하고,

끝 시간인 t가 들어온다면 new Class ( t , -1 )을 저장했습니다.

PQ에서 time으로 오름차순 정렬이 되도록 정렬 조건을 설정해줍니다.

주의해야 할 점은 강의가 끝나는 동시에 새로운 강의가 같은 시간에 시작할 수 있다는 조건입니다.

같은 시간인 경우에 -1, 즉 끝낼 수 있는 강의를 먼저 다 끝낸 후에 새로운 강의가 시작할 수 있도록 정렬 조건을 걸어줍니다.

 

입력을 받고 조건에 따라 PQ에 정렬이 된 후 어떻게 진행이 되는지 보겠습니다.

문제의 질문게시판에서 찾은 예시를 사용해보겠습니다.

5
1 7
2 3
3 4
4 8
7 10

시작시간과 도착시간을 나눠서 정렬한 뒤 결과는

1 1
2 1
3 -1
3 1
4 -1
4 1
7 -1
7 1
8 -1
10 -1

이렇게 나옵니다.

정렬된 결과를 통해 시간이 지남에 따라 사용하고 있는 강의실의 수를 구할 수 있습니다.

 

 

차례대로 말로 풀어본다면,
1 -> 새로운 강의 시작해야해서 강의실이 필요합니다. [ 강의실 +1 ]
2 -> 새로운 강의 시작해야해서 강의실이 필요합니다. = 강의실 +1
3 -> 강의가 끝나서 강의실 하나 비네요. = 강의실 -1
3 -> 새로운 강의 시작해야해서 강의실이 필요합니다. = 강의실 +1
.
.
이런식으로 진행이 되면서 필요한 강의실 수의 max 값을 비교한다면,

최소로 필요한 강의실의 개수를 구할 수 있습니다.

 

 

결과적으로 아래 그림처럼 필요한 강의실 수를 최소한으로 늘려나가면서 강의를 배정할 수 있습니다.

 

 

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
        
        PriorityQueue<Class> pq = new PriorityQueue<>();
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            
            int s = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
                    
            pq.add(new Class(s, 1));
            pq.add(new Class(t, -1));
        }
        
        int max = 0;
        int classroom = 0;
        while(!pq.isEmpty()) {
            Class cur = pq.poll();
            classroom += cur.inout;
            
            max = Math.max(max, classroom);
        }
        System.out.println(max);
        
    }
    static class Class implements Comparable<Class>{
        int time;
        int inout;
        public Class(int time, int inout) {
            this.time = time;
            this.inout = inout;
        }
        @Override
        public int compareTo(Class o) {
            if(this.time==o.time) return this.inout-o.inout;
            return this.time-o.time;
        }
    }
}