[BOJ] 11000 강의실 배정(Java)

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

 

풀이

접근

어려움이 많이 있었던 문제였다.

문제는 단순하게 강의실을 적게 사용하면서 모든 수업을 마치는 것이 목표였다.

 

초기 접근은 과목이라는 객체를 만들어 시작 시간과 끝 시간을 담기로 했다.

과목을 담는 PQ와 강의실 수를 나타내는 PQ를 만들어

과목 PQ에서 꺼낸 과목이 현재 강의실 만으로 충분한지, 아니면 새로운 강의실을 더 빌려야하는지를 판단하고

최종으로 강의실 PQ의 size가 총 사용된 강의실이니 이런식으로 코드를 진행하려했다.

 

그러나 과목이라는 객체가 들어있는 두개의 PQ가 하나는 시작시간이 빠른거, 하나는 종료시간이 빠른거로 꺼낼 수 있어야 하는데,

방법을 모르겠어서 다시 처음부터 생각을 하였다.

 

생각을 하다보니 어차피 강의실은 끝나는 시간만 알고있으면되니, 강의실 PQ를 Integer로 변경하여 풀 수 있었다.

 

코드

package boj;

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

public class Boj11000_강의실배정 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // init
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Subject> pqSubjects = new PriorityQueue<>(); // 강의들을 관리할 우선순위 큐
        PriorityQueue<Integer> pqEndTimes = new PriorityQueue<>(); // 강의 종료 시간을 관리할 우선순위 큐

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            pqSubjects.offer(new Subject(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        // logic
        // 우선순위 큐에 강의가 있는 동안
        while (!pqSubjects.isEmpty()) {
            Subject sj = pqSubjects.poll(); // 가장 빨리 시작하는 강의를 가져옴

            if (!pqEndTimes.isEmpty() && pqEndTimes.peek() <= sj.start) { // 강의실이 비어 있거나 강의가 종료되었을 때
                pqEndTimes.poll(); // 강의실을 비워줌
            }

            pqEndTimes.offer(sj.end); // 현재 강의의 종료 시간을 추가
        }

        System.out.println(pqEndTimes.size()); // 필요한 강의실의 수는 pqEndTimes의 크기
    }

    static class Subject implements Comparable<Subject> {
        int start;
        int end;

        public Subject(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Subject o) {
            if (this.start == o.start)
                return this.end - o.end;
            else
                return this.start - o.start;
        }
    }
}

 

배운점

1. 수도 코드를 짤 때 너무너무 복잡해 보이면 다시 생각해보자.