[Kotlin] BOJ 1263 - 시간 관리

문제 요약

작업마다 (소요시간, 마감시간)이 주어진다. 모든 작업을 순차적으로 처리할 때, 가능한 가장 늦은 시작 시각을 구하는 문제이다. 만약 마감 내에 끝낼 수 없다면 -1을 출력한다.

---

풀이 아이디어

• 각 작업을 마감 시각 기준 내림차순으로 정렬한다.
• 현재 가능한 가장 늦은 시작 시각 curTime을 유지한다.
• 각 작업을 순회하면서
  curTime = min(curTime, endTime) - processTime
  으로 갱신한다.
• 만약 curTime < 0이 되면, 더 이상 모든 작업을 마감 내에 끝낼 수 없으므로 -1을 출력한다.

---

알고리즘 절차

1. 입력을 받아 (processTime, endTime)으로 저장한다.
2. endTime 기준 내림차순 정렬을 한다.
3. curTime을 첫 작업의 endTime으로 초기화한다.
4. 정렬된 작업을 순회하면서:
   • curTime = min(curTime, endTime) - processTime
   • 도중에 curTime < 0이 되면 -1 출력 후 종료
5. 모든 작업이 끝나면 curTime 출력

---

시간 복잡도

• 정렬: O(N log N)
• 순회: O(N)
• 전체: O(N log N)

공간 복잡도

• 작업 배열 저장: O(N)

---

코드 (Kotlin)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer
import kotlin.math.min

data class Work(val processTime: Int, val endTime: Int)

fun main() {
    BufferedReader(InputStreamReader(System.`in`)).use { br ->
        val T = br.readLine().toInt()

        val works = Array<Work>(T) {
            val st = StringTokenizer(br.readLine())
            Work(st.nextToken().toInt(), st.nextToken().toInt())
        }

        works.sortByDescending { it.endTime }
        var curTime = works[0].endTime

        for (i in 0..<works.size) {
            curTime = min(curTime, works[i].endTime) - works[i].processTime
            if (curTime < 0) {
                print(-1)
                return
            }
        }

        print(curTime)
    }
}