백준 19598번: 최소 회의실 개수 (Kotlin)

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

19598번: 최소 회의실 개수

 

풀이

가장 먼저 시작되는 회의에 회의실을 배정한다. 그리고 현재 진행중인 회의들 중 가장 먼저 끝나는 회의와 다음에 시작할 회의의 시작 시간을 비교해서, 진행중인 회의의 끝나는 시간이 더 빠르다면 그 강의실에 새로 시작할 회의를 그대로 넣어준다. 반대로 새로 시작하는 시간이 더 빠르다면 새 회의실을 사용한다. 이렇게 하나씩 비교를 끝마치면, 남아있는 회의의 개수가 지금껏 사용한 회의실의 개수가 된다. 기존의 회의실만 삭제하는 경우는 없으며, 1:1로 교체하거나 추가로 생성만 하기 때문이다.

 

자료구조)

비교를 할 때 남아있는 회의들은 시작 시간순으로 접근하므로, 시작시간의 오름차순으로 정렬을 하고,

진행중인 회의들 중에서는 가장 빨리 끝나는 회의 하나만 꺼내서 비교하므로 끝나는 시간을 기준으로 우선순위 큐(최소힙)를 사용하면 편하게 구현할 수 있다.

 

 

우선순위 큐가 회의실이고, 회의=회의실로 생각해서 교체, 추가한다는 발상이 정말 인상적이었다.

 

코드

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

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val meetings = mutableListOf<Meeting>()
    val pq = PriorityQueue<Meeting>(compareBy{ it.end }) // 현재 진행중인 회의 저장(사용중인 회의실)

    repeat(n){
        val st = StringTokenizer(readLine())
        val meeting = Meeting(st.nextToken().toInt(), st.nextToken().toInt())
        meetings.add(meeting)
    }
    meetings.sortWith(compareBy{ it.start }) // 일찍 시작하는 순서대로 정렬

    pq.add(meetings[0])
    for (i in 1 until n){
        val prevMeeting = pq.peek()   // 진행중인 회의 중 가장 먼저 끝나는 회의
        val nextMeeting = meetings[i] // 다가올 회의 중 가장 먼저 시작하는 회의
        // 기존 회의가 먼저 끝나면 그 회의실에서 다음 회의를 진행할 수 있으므로, 기존 회의를 삭제한다
        if (prevMeeting.end <= nextMeeting.start){
            pq.poll()
        }

        pq.offer(nextMeeting)
    }

    // 회의를 1:1로 교체하거나 회의실이 부족하면 추가 회의실을 사용했기 때문에
    // 남아있는 회의의 개수 = 지금껏 사용한 회의실 개수
    println(pq.size)
}