백준 19598 최소 회의실 개수 Kotlin (우선순위 큐)

문제 출처 : https://www.acmicpc.net/problem/19598

19598번: 최소 회의실 개수

문제

서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자.

입력

첫째 줄에 배열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231−1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최소 회의실 개수를 출력한다.

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 정렬
• 스위핑
• 우선순위 큐

풀이

우선순의 큐를 사용하는 문제이다.

상황을 가정해 보자.

회의실이 두 개가 있고 하나는 30분, 하나는 40분에 끝난다고 하면, 20분에 시작하는 회의가 있다고 할 때 강의실을 하나 더 추가해야 한다

이때 우리는 기존에 회의중인 회의실의 종료시간, 새로 검사하는 회의의 시작 시간을 비교한다.

하지만 기존 회의중인 회의실의 종료시간을 모두 알아야 할까?

가장 빨리 끝나는 시간인 30분만 알면 된다.

회의 중인 회의실에서 가장 빨리 끝나는 시간이 20분이라면 20분 시작 회의를 해당 강의실에서 진행할 수 있고,

회의 중인 회의실에서 가장 빨리 끝나는 시간이 30분이라면 20분 시작 회의는 현재 있는 어떤 강의실에서도 진행할 수 없기 때문이다.

 

이를 바탕으로한 풀이는 다음과 같다.

우선 입력을 회의 시작 시간 기준으로 오름차순 정렬한다.

시작 시간이 빠른 회의가 앞에 오게 되는데, 앞에서부터 pq를 이용해 검사하면 된다.

pq에는 현재 수업의 종료 시간이 들어가고 종료 시간 기준 오름차순이다.

따라서 pq의 front(가장 빠른 종료 시간)와 검사할 회의의 시작 시간을 비교하고, 회의 시작 시간이 front보다 크거나 같다면 해당 회의실에서 회의를 진행할 수 있기 때문에 pq.poll() + pq.add()로 회의 종료 시간을 갱신해 준다.

pq의 특성상 내부적으로 오름차순을 유지하기 때문에 여러 개의 회의실에서 가장 종료시간이 짧은 것을 자동으로 맨 앞으로 보내준다.

 

따라서 pq를 이용하면 간단한 코드로 문제를 풀 수 있고, 이러한 pq의 동작은 O(logN)의 시간 복잡도를 갖고 N개의 회의시간에 대해 탐색하기 때문에 O(NlogN)의 시간 복잡도로 통과할 수 있다.

코드

import java.util.*

val br = System.`in`.bufferedReader()

fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

fun main() = with(System.out.bufferedWriter()) {

    //input
    val n = getInt()
    val input = Array(n) { Pair(0, 0) }
    for (i in 0 until n) {
        val (s, e) = getIntList()
        input[i] = Pair(s, e)
    }

    //solve
    input.sortBy{it.first}
    val pq = PriorityQueue<Int> { a, b ->
        when {
            a < b -> -1
            a == b -> 0
            else -> 1
        }
    }
    pq.add(input[0].second)
    for (i in 1 until n) {
        //시작 시간이 현재 종료 시간보다 큰 경우
        if(pq.peek() <= input[i].first){
            pq.poll()
        }
        pq.add(input[i].second)
    }

    write("${pq.size}")

    close()
}