[백준/코틀린] 1931번: 회의실 배정

링크

1931번: 회의실 배정

풀이

그리디 알고리즘(Greedy Algorithm)이란?
매 순간 가장 좋아 보이는 선택을 하는 알고리즘입니다.
단, 이 방법이 항상 최적해를 보장하려면 탐욕적 선택 속성과 최적 부분 구조가 성립해야 합니다.

종료 시간이 빠른 회의부터 선택하면 가장 많은 회의를 배정할 수 있습니다.

종료 시간이 빠른 회의를 선택하면 남은 시간이 최대화되어
더 많은 회의를 배정할 기회가 생깁니다.

만약 종료 시간이 더 늦은 회의 B를 선택했다면,
B 대신 종료 시간이 빠른 회의 A를 선택해도
A 이후에 선택 가능한 회의 집합이 B 이후보다 항상 크거나 같습니다.
따라서 종료 시간 기준 선택이 최적해를 보장합니다.

회의를 종료 시간 오름차순 → 시작 시간 오름차순으로 정렬한 뒤,
직전 회의의 종료 시간 이후에 시작하는 회의만 선택합니다.

코드

data class Meeting(
    val s: Int,
    val e: Int,
)

fun main() {
    val n = readln().toInt()
    val meetings = List(n) { readln().split(" ").map { it.toInt() } }
        .map { Meeting(it[0], it[1]) }.sortedWith(compareBy(Meeting::e, Meeting::s))
    var lastEndTime = 0
    var ans = 0

    meetings.forEach {
        if (lastEndTime <= it.s) {
            lastEndTime = it.e
            ans++
        }
    }

    println(ans)
}