[Kotlin] 백준 1931 : 회의실 배정

문제 링크

1931번: 회의실 배정

---

---

문제 해설

무엇을 기준으로 정렬을 할지 생각해봐야 할 문제다.

 

회의 시작 시간을 기준으로 정렬하면 (1, 4), (2, 3), (3, 8) 같은 경우엔 최대 2개의 회의를 할 수 있지만 정렬 기준으로 보면 1개의 회의밖에 진행할 수 없다. 그러므로 회의가 끝나는 시간을 기준으로 오름차순 정렬한다. 만약 끝나는 시간이 같은 회의가 같다면 시작하는 시간이 빠른 순서로 정렬한다. 시작 시간을 정렬하지 않으면 회의 시작 시간과 끝 시간이 같은 회의를 카운팅하지 못하는 경우가 생긴다. 예를 들어, (1, 2), (3, 3), (2, 3)이 있을 때 이 순서로 카운팅하면 (2, 3)을 세지 못한다.

 

정렬을 한 이후에는 모든 회의를 순회하면서 회의 시작 시간이 현재 시간 이후인 경우에 카운트를 1 증가시키고 현재 시간을 회의 종료시간으로 세팅하는 과정을 반복한다.

---

Code

import java.util.StringTokenizer
 
fun main() = with(System.`in`.bufferedReader()) {
    val meetings = Array(readLine().toInt()) { StringTokenizer(readLine()).let { Meeting(it.nextToken().toInt(), it.nextToken().toInt()) } }.sortedArray()
    var cnt = 0
    var cur = 0
    for (room in meetings) {
        if (room.start >= cur) {
            cnt++
            cur = room.end
        }
    }
    println(cnt)
}
 
class Meeting(var start: Int, var end: Int) : Comparable<Meeting> {
    override fun compareTo(other: Meeting) = if (this.end == other.end) this.start - other.start else this.end - other.end
}