[구름] 175194 (구름 스퀘어)

import java.io.BufferedReader
import java.io.InputStreamReader

const val START = 0
const val END = 1

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().trim().toInt()

    val events = Array(n) {
        val (s, e) = br.readLine().split(" ").map { it.toInt() }
        intArrayOf(s, e + 1) // e에 1을 더하는 대신, 쿨타임 1시간 조건을 없는 셈 치기
    }

    events.sortWith(compareBy { it[END] })

    var count = 0
    var lastEnd = -1

    for (event in events) {
        if (event[START] >= lastEnd) {
            count++
            lastEnd = event[END]
        }
    }

    println(count)
}

표기된 난이도에 비해 꽤 시간이 걸린 문제다. 왜냐하면 이 문제가 그리디 알고리즘이 적용될 수 있는 문제라는 걸 깨닫지 못했기 때문이다. 즉 상대방의 정체도 파악하지 못한 채 머리를 싸매고만 있었다. 석연(?)치 않아도 뭔가 정렬을 쓸 것 같다는 느낌이 오면, 한 번 시도해 보고 어떤 양상인지 확인하는 습관을 들여도 좋겠다. 이 문제를 예로 들면, s와 e 각각에 대해 오름차순으로도 정렬해 보고 내림차순으로도 정렬해 보는 것이다.