[백준/11000] 강의실 배정 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/11000
• 분류 : 우선순위큐
• 풀이 시간 : 40분

문제 해설

1. Si에 시작해서 Ti에 끝나는 N개의 수업이 주어짐
2. 모든 수업을 가능하게하는 최소 강의실의 개수는?

Solution

풀이 접근 방법

1. 최대한 많은 강의 진행하는 문제 ~ -> "끝나는 시간 오름차순 정렬"이라고 생각하고 풀면 틀림!!

   1. 끝나는 시간 오름차순은 하나의 강의실에서 최대한 많은 수업을 진행하려할 때 해당됨!!

2. 강의실이 비는 시간을 최소화 해야 함 = 강의 끝나는 시간과 다음 강의 시작 시간 사이의 텀이 작아야 함

   1. 강의 시간 오름차순 정렬해서 끝나는 대로 빨리 시작하는 강의 넣어야 함
   2. 반례 확인
      

3. 강의 시간 오름차순 -> 강의 정보 객체(Session Class) 만들어서 우선순위 큐에 넣고 하나씩 뺌

4. 빨리 끝나는 강의 알기 위해 -> 강의 끝나는 시간을 우선순위 큐에 넣고 관리

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
  static class Session implements Comparable<Session> {
    int start, end;

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

    @Override
    public int compareTo(Session o) {
      // 시작시간 오름차순
      if (Integer.compare(this.start, o.start) == 0) {
        // 시작시간이 같다면, 종료시간 오름차순
        return Integer.compare(this.end, o.end);
      }
      return Integer.compare(this.start, o.start);
    }
  }

  static int N;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    N = Integer.valueOf(br.readLine());
    // 시간시간 오름차순 순서대로 강의 담음
    PriorityQueue<Session> sessions = new PriorityQueue<Session>();

    for (int i = 0; i < N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int start = Integer.valueOf(st.nextToken());
      int end = Integer.valueOf(st.nextToken());

      sessions.add(new Session(start, end));
    }

    // 강의실 개수 변수 : 1개로 시작
    int classCnt = 1;
    // 강의실별 끝나는 시간을 저장하는 큐 : 빨리 끝나는 강의싱이 우선순위 높음
    // 큐의 사이즈 = 오픈한 강의실 개수
    PriorityQueue<Integer> endQueue = new PriorityQueue<>();
    // 첫 강의실에서 진행하는 강의의 끝나는 시간 넣음
    endQueue.add(sessions.poll().end);

    // 모든 강의가 강의실에 들어갈 때 까지
    while (!sessions.isEmpty()) {
      Session current = sessions.poll();

      // 제일 빨리 끝나는 강의실의 종료 시간이 현대 시작해야할 강의보다 빠르면
      if (endQueue.peek() <= current.start) {
        // 해당 강의실 수업 종료
        endQueue.poll();
      } else {
        // 제일 빨리 끝나는 강의보다 시작 시간이 더 빠르면
        // 새로운 강의실 오픈
        classCnt++;
      }
      // 수업 종료한 강의실 || 새로 오픈한 강의실에 강의 넣음
      endQueue.add(current.end);
    }

    bw.write(classCnt + "\n");
    bw.flush();
    bw.close();
  }

}