마감시간이 있는 스케쥴 짜기

  • 마감시간과 함께 여러개의 작업이 주어지고 마감시간 내에 마치면 보상이 주어짐
  • 이 보상이 최대가 되는 스케쥴을 작성하는 문제

Greedy Approach로 해결하기

  • 보상에 따라서 비오름차순으로 작업을 정렬하고 각 작업을 순서대로 하나씩 가능한 스케쥴에 포함시킴

슈도 코드로 작성해보기

1
2
3
4
5
6
7
S = ∅
while (답을 구하지 못함):
    다음 작업을 선택
    if (이 작업을 추가했을 때 S가 적절함)
        이 작업을 S에 추가
    if (더 이상 남은 작업이 없다면)
        답을 구하였으니 return
  • 적절함 의 정의
    • 어떤 순서는 그 순서 내의 모든 작업이 데드라인 이전에 시작될 때 적절한 순서라 한다
      예) [4,1]은 정렬된 데드라인이라 적절하나 [1,4]는 부적절함
    • 어떤 집합은 그 집합의 원소들로 하나 이상의 적절한 순서를 만들 수 있을 때 적절한 집합이라 한다
      예) 집합 {1,4}는 [4,1]을 구성할 수 있으므로 적절한 집합임

파이썬으로 구현하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def schedule (deadline):
    n = len(deadline) - 1
    J = [1]
    for i in range(2, n + 1):
        K = insert(J, i, deadline)
        if(feasible(K, deadline)):
            J = K[:] # 파이썬에서 배열의 깊은 복사
    return J

def feasible(K, deadline):
    for i in rage(1, len(K) + 1):
        if (i > deadline[K[i - 1]]):
            return False
    return True


def insert(J, i, deadline):
    K = J[:]
    for j in range(len(J), 0, -1):
        if (deadline[i] >= deadline[K[j-1]]):
            j += 1
            break
    K.insert(j - 1, i)
    return K