[kotlin] 회의실 배정

 

 

문제 접근 방법

• 회의를 끝나는 시간 기준으로 정렬
• 겹치지 않는 회의만 선택
• 그리디 알고리즘으로 최적의 결과 도출

package com.chanhue.algorithm.백준.골드

fun main() {

    // 회의의 개수를 입력받음
    val n = readln().toInt()

    // 회의 정보를 저장할 리스트 (Pair: (시작시간, 종료시간))
    val meetings = mutableListOf<Pair<Int, Int>>()

    // 회의 정보 입력받기
    repeat(n) {
        val (start, end) = readln().split(" ").map { it.toInt() }
        // Pair 생성자를 이용해 리스트에 추가
        meetings.add(Pair(start, end))
    }

    // 회의들을 종료 시간이 빠른 순서로 정렬
    // 종료 시간이 같을 경우 시작 시간이 빠른 순서로 정렬
    meetings.sortWith(compareBy({ it.second }, { it.first }))

    var count = 0         // 선택한 회의 개수
    var endTime = 0       // 이전 회의가 끝난 시간

    // 정렬된 회의 리스트를 순회
    for ((start, end) in meetings) {
        // 현재 회의의 시작 시간이 이전 회의의 종료 시간과 겹치지 않는 경우
        if (start >= endTime) {
            count++        // 회의 개수 증가
            endTime = end  // 다음 회의 선택을 위해 현재 회의의 종료 시간 저장
        }
    }

    // 선택할 수 있는 최대 회의 개수 출력
    println(count)
}