강의실 배정

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

3
1 3
2 4
3 5

예제 출력 1

2

문제 풀이

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 BJ11000_Classroom {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N=Integer.parseInt(br.readLine());
        long ans=0;

        // 강의실
        PriorityQueue<Long> queue=new PriorityQueue<>();
        // 수업
        long[][] course=new long[N][2];

        for(int i=0;i<N;i++){
            st=new StringTokenizer(br.readLine());
            course[i][0]=Long.parseLong(st.nextToken());
            course[i][1]=Long.parseLong(st.nextToken());
        }

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

        for(int i=0;i<N;i++){
            if(queue.isEmpty()){
                ans++;
                queue.offer(course[i][1]);
                continue;
            }

            // 현재 사용중인 강의실이 끝나는 시간보다 다음 수업의 시작 시간이 빠르다면
            if(course[i][0]<queue.peek()){
                ans++;
                queue.offer(course[i][1]);
            }else{
                queue.poll();
                queue.offer(course[i][1]);
            }
        }

        System.out.println(ans);
    }
}

모든 수업을 할 수 있도록 하는 강의실의 최소 개수를 구하는 문제이다.

이미 수업중인 강의실이 있다면 해당 강의실의 수업이 끝나는 시간보다 다음 수업이 시작하는 시간이 같거나 커야한다.

예를 들어

1 3
1 4
2 4
3 5

위와 같은 예시가 있다면

• A 강의실에 1-3 의 수업을 넣고
• B 강의실에 1-4 수업을 넣고
• 2의 시간까지도 A, B 강의실 모두 수업이 끝나지 않았기 때문에 C 강의실에 2-4 수업을 넣는다.
• 3의 시간이 되면 A 강의실 수업이 끝나기 때문에 3-5의 시간을 넣을 수 있다.

즉, 수업 시작시간이 강의실의 수업이 끝나는 시간보다 크거나 같다면 강의실을 늘릴 필요가 없는 것이다.

이 점을 이용하여 문제를 풀면 쉽게 풀 수 있다.

수업 정렬하기

// 수업
long[][] course=new long[N][2];

for(int i=0;i<N;i++){
    st=new StringTokenizer(br.readLine());
    course[i][0]=Long.parseLong(st.nextToken());
    course[i][1]=Long.parseLong(st.nextToken());
}

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

수업 정보는 course라는 이중 배열에 넣어주고 Comparator를 이용하여 시작시간을 기준으로 정렬해준다.

만약 시작시간이 같은 수업이 있다면 끝나는 시간이 더 빠른 경우를 앞으로 정렬한다.

강의실 배정

// 강의실
PriorityQueue<Long> queue=new PriorityQueue<>();

for(int i=0;i<N;i++){
    if(queue.isEmpty()){
        ans++;
        queue.offer(course[i][1]);
        continue;
    }
    
    // 현재 사용중인 강의실이 끝나는 시간보다 다음 수업의 시작 시간이 빠르다면
    if(course[i][0]<queue.peek()){
        ans++;
        queue.offer(course[i][1]);
    }else{
        queue.poll();
        queue.offer(course[i][1]);
    }
}

강의실 배정을 위해 사용중인 강의실 정보를 저장하기 위해 우선순위큐를 이용했다.

수업이 끝나는 시간을 큐에 저장하고 오름차순으로 정렬되게 하면 가장 빠르게 끝나는 수업부터 확인할 수 있다.

모든 수업 정보를 확인하기위해 반복문을 돌리고

• queue가 비어있다면 (강의실에 아무런 수업도 배치가 되지 않은 상황이라면)

강의실 개수를 늘려주고 수업이 끝나는 시간값을 큐에 넣어준다.

• queue가 채워져있는 상황이라면 (강의실에서 수업을 하고 있는 중이라면)

다음 수업이 시작하는 시간과 현재 수업중인 수업 중 가장 빠르게 끝나는 수업을 확인하여 강의실을 새로 배정해야하는지 확인한다.

즉, 다음 수업이 시작하는 시간이 가장 빠르게 끝나는 수업시간보다 빠르다면 현재 강의실을 이용할 수 없기 때문에 새로운 강의실을 늘려주고 큐에 다음 수업이 끝나는 시간 값을 넣어준다.

• 반대로 다음 수업시간보다 현재 수업중인 수업이 끝나는 시간이 빠르다면

강의실을 늘리지 않고 사용할 수 있기 때문에 수업이 끝난 정보를 큐에서 빼주고 다음 수업이 끝나는 시간 정보를 큐에 넣어주는 작업을 반복해준다.

이 작업을 모두 끝내면 필요한 강의실의 최소 개수를 구할 수 있다.