[leetecode 오늘의 문제] 1235. Maximum Profit in Job Scheduling

오늘의 문제 링크

 

오늘의 문제는 Job Scheduling 을 하면서, Maximum Profit 을 찾는 문제였다.

얼핏 봤을 때는 지난번에 풀었던 Interval Scheduling Algorithm 이 생각났다. Interval Scheduling Algorithm 은 일반적으로 각 간격과 관련된 이익을 고려하지 않고 겹치지 않는 간격(또는 작업)의 수를 최대화하는 것이었다.

 

하지만 이번 문제에서는 총 이익을 극대화해야 하므로 복잡도가 올라갔고, 다른 방법으로 접근해야 했다.

 

---

1. 종료 시간을 기준으로 정렬

Interval Scheduling Algorithm 이랑 비슷한 부분은 종료 시간을 기준으로 정렬하고 시작한다는 것

종료 시간을 기준으로 정렬하는 것은 현재 직업 이후에 선택할 수 있는 다음 직업을 효율적으로 찾을 수 있도록 해준다.

    jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])

 

2. 동적 프로그래밍(DP) 접근

1. DP 테이블 생성:
   1. 테이블의 각 항목 dp[i]는 정렬된 job 목록에서 처음 i개의 job을 고려할 때 얻을 수 있는 최대 이익을 나타낸다.
2. 각 job에 대한 결정: 
   • job을 제외하는 경우, 이익은 이전 job[i-1]과 동일하게 유지된다.
     • dp[i] = dp[i-1]
   • job을 포함하는 경우, 해당 job의 이익을 추가해야 하며, 또한 현재 job의 시작 시간 전에 끝나는 충돌하지 않는 이전 job에서 얻을 수 있는 최대 이익을 추가해야 합니다.
3. 최대 이익 계산: 각 job에 대해 이 두 가지 선택 사이에서 더 높은 이익을 주는 선택을 하여 최대 이익을 계산합니다.

    for i in range(1, n+1):
        # 옵션 1: 현재 job 을 제외
        excl = dp[i-1]

        # 옵션 2: 현재 job 을 포함
        incl = jobs[i-1][2]
        lastNonConflict = binarySearch(jobs, i-1)
        if lastNonConflict != -1:
            incl += dp[lastNonConflict + 1]

        # 현재 job 을 제외했을 때와 포함했을 때 이익이 최대화되는 경우를 dp[i]에 저장
        dp[i] = max(excl, incl)

 

(1) binarysearch

binarysearch를 사용하는 이유는 현재 작업과 시간상으로 겹치지 않으면서 가능한 가장 늦게 끝나는 이전 작업을 효율적으로 찾기 위해서다. job들이 종료 시간에 따라 정렬되어 있기 때문에, binarysearch는 현재 작업의 시작 시간 이전에 끝나는 가장 마지막 작업을 빠르게 찾는데 효율적인 방법이다.

• binarysearch는 정렬된 리스트에서 특정 값을 찾을 때 효율적인 방법으로, 평균적으로 O(log n) 시간 복잡도를 가진다.
• 이는 각 작업을 처리할 때마다 모든 이전 작업을 확인하는 O(n) 시간 복잡도를 가지는 선형 탐색보다 훨씬 빠르다.

    def binarySearch(jobs, index):
        low, high = 0, index - 1
        while low <= high:
            mid = (low + high) // 2
            if jobs[mid][1] <= jobs[index][0]:
                if jobs[mid + 1][1] <= jobs[index][0]:
                    low = mid + 1
                else:
                    return mid
            else:
                high = mid - 1
        return -1