백준 11000 강의실 배정

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

시작 시간 - 종료 시간으로 이루어진 수업이 N개 주어진다.
모든 수업을 가능하게 하는 강의실 개수의 최솟값을 구하는 문제이다.

정렬과 Priority Queue를 이용해 문제를 풀이하였다.

1. 강의들을 시작 시간 기준으로 정렬한다.

2. 최솟값을 반환하는 최솟값 Priority Queue를 생성한다.

3. 정렬한 강의들을 순회하며 강의의 종료 시간을 PQ에 넣는다.
   만약 현재 강의의 시작 시간이 PQ에서 가장 작은 값(종료 시간)과 같거나 크다면, PQ에서 값을 뽑은 후 현재 강의의 종료 시간을 넣는다 (붙인다)

4. 모든 강의를 순회한 후 PQ의 크기가 강의실 개수가 된다.

(1, 3) (2, 4) (3, 5) (2, 7) (1, 8) (7, 9) (5, 10)을 예로 들어보자.

1. 시작 시간 기준 정렬
   (1, 3) (1, 8) (2, 4) (2, 7) (3, 5) (5, 10) (7, 9)

2. Priority Queue 생성.

3. 순회하며 비교한다.
   (1, 3) - PQ가 비었으므로 PQ에 종료 시간인 3을 넣는다.
   (1, 8) - PQ의 다음 값이 3이고, 현재 강의 시작 시간이 1이므로 강의를 붙일 수 없다. 따라서 PQ에 종료 시간인 8을 넣는다.
   (2, 4) - PQ의 다음 값이 3이고, 현재 강의 시작 시간이 2이므로 PQ에 종료 시간인 4를 넣는다.
   (2, 7) - 위와 동일하게 PQ에 7을 넣는다.
   (3, 5) - PQ의 다음 값이 3이고, 현재 강의 시작 시간이 3이므로 강의를 붙일 수 있다. 따라서 PQ에서 3을 빼고 5를 넣는다 - (1, 3)과 (3, 5)를 붙임.
   (5, 10) - PQ의 다음 값이 4이고, 현재 강의 시작 시간이 5이므로 강의를 붙일 수 있다. 따라서 PQ에서 4를 빼고 10을 넣는다 - (2, 4)와 (5, 10)을 붙임
   (7, 9) - PQ의 다음 값이 5이고, 현재 강의 시작 시간이 7이므로 강의를 붙일 수 있다. 따라서 PQ에서 5를 빼고 9를 넣는다.

따라서 PQ에는 7, 8, 9, 10으로 4개의 종료 시간을 가진 강의실이 존재한다.

여기서 의문을 가질 수 있다.

(1, 3) (3, 5) (5, 10)
(1, 8)
(2, 7) (7, 9)
(2, 4)

위처럼 가능하면 기존 수업의 종료 시간과 다음 수업의 시작 시간을 가능한 맞춰야 최적이 되지 않을까 생각할 수도 있다.

위 풀이로 구한 강의실 수업 진행은 아래와 같다.

(1, 3) (3, 5) (7, 9)
(1, 8)
(2, 4) (5, 10)
(2, 7)

이것이 가능한 이유는 시작 시간으로 정렬하는 데에 있다.

(1, 3) (3, 5)
(1, 8)
(2, 4)
(2, 7)

위 상태에서 다음 넣을 강의가 (7, 9)라고 가정하자.

강의들은 시작 시간 기준으로 정렬되어 있으므로 (7, 9)를 꼭 7 뒤에 붙이지 않아도, 5부터 시작하거나 6부터 시작하는 강의가 없다는 것을 보장할 수 있다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val lectures = Array(N){
        val (start, end) = readLine().split(' ').map{it.toInt()}
        Lecture(start, end)
    }.sortedArrayWith{l1, l2 -> l1.start - l2.start}

    val rooms = PriorityQueue<Int>()
    for(lec in lectures){
        if(rooms.isEmpty()){
            rooms.offer(lec.end)
            continue
        }

        if(rooms.peek() <= lec.start){
            rooms.poll()
            rooms.offer(lec.end)
        }else
            rooms.offer(lec.end)
    }

    print(rooms.size)
}

data class Lecture(
    val start: Int,
    val end: Int
)