(Kotlin) 백준 6068번 - 시간 관리하기

https://www.acmicpc.net/problem/6068

6068번: 시간 관리하기

유형

정렬, 그리디 or 특정 알고리즘 X

풀이

풀이 순서

1. 일을 시작하는 시간(startTime)과 마지막 시간(endTime)으로 변환한다.

2. endTime이 가장 늦은(큰) 일부터 차례대로 최대한 늦게 일을 시작하도록 일의 시간을 확정 짓는다.

  => 따라서, 위 과정에 앞서 endTime 기준 내림차순으로 정렬한다.

3. 가장 빨리 시작하게 될 일의 startTime을 출력한다.

1. 일을 시작하는 시간(startTime)과 마지막 시간(endTime)으로 변환한다.

일을 시작하는 시간(startTime)과 마지막 시간(endTime)으로 변환한다.

ex) 걸리는 시간: 5, 끝내야 하는 시간 9 => endTime: 9 - 1 = 8, startTime: endTime - 5 + 1 = 4

이렇게 놓으면 endTime 바로 다음인 끝내야 하는 시간에 일이 끝나있게 된다.

data class Task(var start: Int, var end: Int)

repeat(taskSize) {
    val (duration, dueTime) = readLine().split(" ").map(String::toInt)
    taskList.add(Task(dueTime - duration, dueTime - 1))
}

2. endTime 값이 가장 큰 일부터 차례대로 최대한 늦게 일을 시작하도록 배치한다.

가장 늦게 일어나기 위해서 모든 일을 데드라인에 최대한 가깝게 배치하며, endTime 값이 가장 큰 task부터 스케줄을 확정한다. task(currentTask)를 스케줄할 때 직전에 배치한 task(nextTask)와 비교해서 타임 라인이 겹친다면, currentTask를 nextTask 바로 왼쪽으로 배치한다. 이렇게 하면 현재 상황에서 currentTask를 최대한 늦은 시간에 스케줄한 것이 된다.

 

ex) currentTask: task C, nextTask: task D

 

단, currentTask를 왼쪽으로 옮기는 과정에서 startTime < 0이 된다면, 제시간에 일을 끝낼 수 없다는 의미가 된다.

var prevTask = taskList[0]
for (i in 1 until taskSize) {
    val currentTask = taskList[i]

    // prevTask과 currentTask의 시간이 겹치는 부분이 있거나, 통째로 currentTask가 더 오른쪽에 있는 경우
    // -> currentTask를 겹치지 않게 왼쪽 옮긴다
    if (currentTask.end >= prevTask.start){ // currentTask가 prevTask에 걸쳐있는 경우
        val moveToLeftTime = currentTask.end - prevTask.start + 1
        currentTask.end -= moveToLeftTime
        currentTask.start -= moveToLeftTime
    }
    
    if (currentTask.start < 0) {
        print(-1)
        return
    }
    prevTask = currentTask
}

3. 가장 빨리 시작하게 될 일의 startTime을 출력한다.

위에서 수평선 기준 오른쪽에 있는 task부터 겹치지 않으면서 데드라인에 가깝게 배치하고 나면, 맨 왼쪽에 있는 task의 startTime이 일을 가장 늦게 시작할 수 있는 시간이 된다.

코드

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

// start: 일 시작 시간, end: 마지막 시간 -> end+1 시간에는 작업이 끝나있다 
data class Task(var start: Int, var end: Int)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val taskSize = readLine().toInt()
    val taskList = mutableListOf<Task>()

    repeat(taskSize) {
        val (duration, dueTime) = readLine().split(" ").map(String::toInt)
        val task = Task(dueTime - duration, dueTime - 1)
        taskList.add(task)
    }

    // 가장 늦게 끝낼 일이 먼저 오도록 정렬
    taskList.sortByDescending { it.end } 

    // 비교 기준, 시간상 currentTask 바로 다음에 진행할 task
    var nextTask = taskList[0]
    
    for (i in 1 until taskSize) {
        val currentTask = taskList[i]

        // nextTask currentTask의 시간이 겹치는 부분이 있거나, 통째로 current가 더 오른쪽에 있으면
        // 겹치지 않게 current가 nextTask 직전에 끝나게 왼쪽으로 옮긴다
        if (currentTask.end >= nextTask.start){
            val moveToLeft = currentTask.end - nextTask.start + 1
            currentTask.end -= moveToLeft
            currentTask.start -= moveToLeft
        }

        // currentTask를 0초 이전에 시작해야 하면 -1 반환
        if (currentTask.start < 0) {
            print(-1)
            return
        }
        
        nextTask = currentTask // 비교 기준 갱신
    }

    print(taskList.last().start) // 가장 먼저 시작할 task의 시작 시간
}