[자바로 푸는 백준] 11000번 강의실 배정

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

11000번: 강의실 배정

✅ 골드 Ⅴ

 

🔶 풀이

해당 문제는 완전 탐색으로 진행하면 시간 초과가 발생한다.

때문에 정렬과 우선순위 큐를 이용해서 해결할 수 있다.

 

예제 1번

위 그림은 예제 1번을 보기 좋게 표현했다.

수업이 끝난 직후에 다음 수업을 시작할 수 있다고 했으므로 강의실 2개를 사용한다.

 

우선, 시작 시간을 기준으로 오름차순 정렬을 해줘야된다.

마감 시간을 기준으로 오름차순 정렬하게 되면 아래와 같은 상황에서 반례가 발생한다.

 

4

1 2

1 4

2 6

4 5

 

1. (1,2)

강의실 A: (1,2)

 

2. (1,4)

강의실 A: (1,2)

강의실 B: (1,4)

 

3. (4,5)

강의실 A: (1,2), (4,5)

강의실 B: (1,4)

 

4. (2,6)

강의실 A: (1,2), (4,5)

강의실 B: (1,4)

강의실 C: (2,6)

 

마감 시간을 기준으로 정렬했을 경우, 3개의 강의실을 사용한다고 출력된다. 하지만 수업 시작시간으로 오름차순 정렬을 하게 되면 정답은 2가 된다.

 

시작 시간을 기준으로 정렬을 했다면 우선순위 큐를 이용해서 수업을 하나씩 살펴보면 된다.

우선순위 큐에 마감 시간을 넣어주고, 배정되지 않은 강의의 시작 시간을 비교해 준다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(lesson[0].e);
                
for (int i=1; i<N; i++) {
    if (pq.peek() <= lesson[i].s) {
        pq.poll();
    }
            
    pq.add(lesson[i].e);
}

현재 강의 마감 시간 <= 배정되지 않은 강의의 시작 시간: 우선순위 큐에서 제거 

현재 강의 마감 시간 >  배정되지 않은 강의의 시작 시간: 우선순위 큐에 추가 (강의실 추가)

 

위와 같은 방식으로 모든 강의를 탐색한 후에 우선순위 큐의 크기가 정답이 된다.

 

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    public static class Lesson implements Comparable<Lesson>{
        int s, e;
        
        public Lesson (int s, int e) {
            this.s = s;
            this.e = e;
        }
        
        // 수업 시작 시간을 오름차순 정렬
        // 수업 시작 시간이 같을 경우, 시작 마감 시간을 오름차순 정렬
        public int compareTo(Lesson o) {
            if (this.s == o.s) {
                return this.e - o.e;
            }
            
            return this.s - o.s;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine()); // 수업 개수
        Lesson[] lesson = new Lesson[N];
        
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            
            lesson[i] = new Lesson(S, E);
        }
        
        Arrays.sort(lesson);
        
        // 수업 마감 시간을 입력하기 위한 우선순위 큐
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(lesson[0].e);
                
        for (int i=1; i<N; i++) {
            if (pq.peek() <= lesson[i].s) {
                pq.poll();
            }
            
            pq.add(lesson[i].e);
        }
        
        System.out.println(pq.size());
    }
}