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

링크

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

---

입력 예제

3
1 3
2 4
3 5

---

출력 예제

2

---

풀이

우선 모든 강의들을 시작 시간을 기준으로 정렬한다. 그리고 순서대로 우선 순위 큐에 삽입하여 종료 시간을 빠른 순서대로 정렬한다.

예제를 기준으로 생각해보면 우선 (1, 3) 강의부터 큐에 추가된다.

• 3 (종료 시간 삽입)

그리고 다음 강의는 (2, 4)이며 앞선 강의의 종료 시간인 3보다 시작 시간이 빠르므로 새로운 강의실을 사용한다.

• 3, 4

그 다음 강의는 (3, 5)이며 제일 빠른 종료 시간이 3이고, 따라서 기존 강의실을 사용할 수 있게 된다.

• 4, 5

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/*
백준 / 강의실 배정 / 골드5
https://www.acmicpc.net/problem/11000
 */
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());
        List<Lecture> lectures = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            lectures.add(new Lecture(start, end));
        }

        lectures.sort(Comparator.comparingInt(o -> o.start));  //강의 시작 시간을 기준으로 정렬
        PriorityQueue<Integer> endTimes = new PriorityQueue<>();  //종료 시간만 관리

        for (Lecture lecture : lectures) {
            int start = lecture.start;
            int end = lecture.end;

            if (!endTimes.isEmpty() && endTimes.peek() <= start) {  //사용 가능한 강의실이 있을 때
                endTimes.poll();  //기존 강의실 사용
                endTimes.add(end);
            } else {
                endTimes.add(end);  //새 강의실 추가
            }

        }

        System.out.println(endTimes.size());
    }

    static class Lecture {
        int start;
        int end;

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