작업 선택 문제를 다루는 다음 알고리즘은 각 작업의 시작 시간 s와 완… | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지

작업 선택 문제를 다루는 다음 알고리즘은 각 작업의 시작 시간 s와 완료 시간 f가 정해진 $n$개의 작업 t[0..n-1]가 주어질 때, 하나의 기계만 사용하여 충돌 없이 수행할 수 있는 최대 개수의 작업을 선택한다. 이 알고리즘의 (가), (나)에 들어갈 내용을 바르게 연결한 것은? (단, n ≥ 2인 정수, count는 선택한 작업의 개수, t[i].s는 작업 t[i]의 시작 시간, t[i].f는 작업 t[i]의 종료 시간이고, jobs 배열은 선택된 작업을 저장한다)
ActSelect(n, t[]) {
    (가) 의 오름차순으로 작업 t[]를 정렬;
    count = 0, last = 0, jobs[];
    jobs[count] = 0;
    for(i = 0; i < n; i++)
        if( (나) ) {
            count++;
            last = i;
            jobs[count] = last;
        }
    return jobs;
}

(가) 시작 시간 / (나) t[i].s >= t[last].f

(가) 시작 시간 / (나) t[i].f >= t[last].s

(가) 완료 시간 / (나) t[i].s >= t[last].f

(가) 완료 시간 / (나) t[i].f >= t[last].s

(가)는 완료 시간, (나)는 t[i].s >= t[last].f이다.
작업 선택 문제의 탐욕 전략은 가장 일찍 끝나는 작업부터 고르는 것으로, 그래야 남은 시간에 더 많은 작업을 넣을 수 있다.
정렬 후에는 현재 작업의 시작 시간이 마지막으로 선택한 작업의 종료 시간 이후일 때만 충돌이 없으므로 선택한다.
시작 시간 순으로 정렬하면 일찍 시작하지만 오래 걸리는 작업이 먼저 뽑혀 최대 개수를 보장하지 못한다.
시작 시간 순 정렬에 종료·시작 시간을 비교하는 조건은 정렬 기준과 겹침 판정이 모두 틀렸다.
완료 시간 순 정렬이라도 현재 작업의 종료 시간과 마지막 작업의 시작 시간을 비교하면 시간 겹침을 막지 못한다.