[백준 11000번] [Kotlin] 강의실 배정

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

11000번: 강의실 배정

 

난이도 : 골드 5
태그 : 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐

 

 

설명

한 시간대에 동시에 진행중인 강의가 몇 개인지 체크하는 문제입니다.

가장 처음 든 생각은 아무래도 int 배열을 체크해놓고 하나씩 체크해볼까? 생각했지만,

 시작, 끝 시간의 범위 (0 ≤ Si < Ti ≤ 109)를 보고 바로 다른 방법을 고민하였습니다.

 

아무래도 우선순위 큐를 사용해 그리디적으로 풀 수 있을 것 같네요.

 

위와 같이 그림으로 그려 나타내면 쉬울 것 같습니다.

왼쪽 끝은 시작, 오른쪽 끝은 끝나는 시간을 시간 막대 그래프로 표현한다면,

가장 많이 겹치는 구간(3개)을 확인할 수 있습니다.

 

그럼, 가장 많이 겹치는 구간을 찾으려면 어떻게 해야 할까요?

 

일단 시작이 빠른 순서로 정렬 합니다.

이후, 첫 번째 일정부터 종료시간을 우선순위 큐에 넣습니다. (이 때 우선순위 큐는 Int 내림차순 입니다.)

첫 번째 일정은 1~3이니, 큐에는 3가 들어있겠네요.

현재 큐 : 3

 

두 번째 일정(2~5)의 종료시간도 큐에 넣습니다.

이때, 두 번째 일정의 시작시간인 2 보다 큐의 맨 윗값(peek)인 3이 더 큽니다.

즉, 이 두 강의는 서로 겹치는 시간이 있음을 의미하므로, 강의실은 2개가 필요합니다.

현재 큐 : 3, 5

 

세 번째 일정(3~7)의 종료시간도 큐에 넣습니다.

세 강의는 모두 겹치는 시간이 존재하므로, 강의실은 3개가 필요합니다.

현재 큐 : 3, 5, 7

 

네 번째 일정(4~8)의 종료시간도 큐에 넣습니다.

앗, 그런데 현재 큐의 맨 윗값(peek)이 네 번째 일정의 시작시간(4)보다 큽니다.

즉, 큐의 맨 위에 있는 일정과 네 번째 일정은 겹치는 시간이 없음을 의미합니다!

큐의 맨 윗값이 현재 강의의 시작시간보다 작거나 같을 때 까지 큐에서 뺍니다!

현재 큐 : 5, 7, 8 (3 poll, 8 offer)

큐에서 모두 다 뺀 후, 큐의 크기는 3입니다. 강의 3개가 동시에 진행되고 있다는 의미입니다.

 

위 과정을 반복하며,

우선순위 큐에 종료 시간을 넣고,

큐의 맨 윗값보다 현재 시간이 클 동안 poll을 해줍니다.

이 때, 큐의 크기가 곧 동시에 진행되는 강의의 개수를 의미하므로,

result 값을 더 큰 값으로 갱신시킵니다.

 

 

 

 

소스코드

import java.util.PriorityQueue
import java.util.StringTokenizer

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

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()

    val lectures = Array(n) {
        val st = StringTokenizer(readLine())
        Lecture(st.nextToken().toInt(), st.nextToken().toInt())
    }.sortedWith(compareBy { it.start })

    var result = 0
    val pq = PriorityQueue<Int>()

    lectures.forEach { lecture ->
        pq.offer(lecture.end)

        while (pq.isNotEmpty() && pq.peek() <= lecture.start) {
            pq.poll()
        }

        result = maxOf(result, pq.size)
    }

    println(result)
}

 

 

 

 

후기

정렬 + 우선순위 큐 + 그리디 조합은 이전에도 몇 번 풀어봤던 터라,

아이디어 자체는 빠르게 떠올려 풀 수 있었습니다.

하지만 블로그에 설명을 적으려 하니 뭐라 적어야 할지 다소 난해했던 것 같네요ㅠ

역시 배우는 것보다 설명하기가 훨씬 어려운 것 같습니다.