1235. Maximum Profit in Job Scheduling
✨ 문제 요약
- n개의 작업이 있고, 각각
- 시작 시간 startTime[i]
- 끝나는 시간 endTime[i]
- 이익 profit[i]
- 서로 겹치지 않게 작업을 선택하면서
얻을 수 있는 최대 이익을 구하는 문제.
✨ 핵심 풀이 아이디어
이건 "배낭 문제 (Knapsack Problem)" + "이진 탐색" 조합 문제야.
흐름:
- 일들을 (start, end, profit) 튜플로 정리하고, endTime 순서대로 정렬한다.
- dp[i] = i번째 작업까지 고려했을 때 얻을 수 있는 최대 이익 저장.
- 각 작업에 대해:
- 이 일을 선택하지 않을지 (dp[i-1])
- 이 일을 선택할지 (현재 profit + 이전에 겹치지 않는 일까지 최대 profit)
- 둘 중 큰 걸 고른다.
- 겹치지 않는 마지막 일은 binary search로 찾는다.
import bisect
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
# (start, end, profit) 묶어서 endTime 기준으로 정렬
jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
# dp[i]: i번째 작업까지 고려했을 때 얻을 수 있는 최대 이익
dp = [(0, 0)] # (endTime, maxProfit) - 초기값: 끝나는 시간 0에 이익 0
for s, e, p in jobs:
# 이 작업을 시작할 수 있는 가장 마지막 작업 찾기
# dp 리스트에서 끝나는 시간이 s보다 작거나 같은 가장 큰 endTime을 찾음
i = bisect.bisect_right(dp, (s, float('inf'))) - 1
if i >= 0:
# 이전 최대 이익 + 현재 작업 이익
curProfit = dp[i][1] + p
# 현재 저장된 최대 이익(dp[-1][1])보다 이익이 더 커야만 추가
if curProfit > dp[-1][1]:
dp.append((e, curProfit))
# 마지막 dp에 저장된 최대 이익 리턴
return dp[-1][1]✨ 흐름 정리
- 작업들을 끝나는 시간 기준으로 정렬
- dp 테이블은 (endTime, maxProfit) 형태로 저장
- 각 작업마다
- 시작 시간 전에 끝나는 가장 가까운 작업을 binary search로 찾고
- 그 작업까지의 최대 이익 + 현재 profit을 더해서 갱신
- 항상 최대 이익을 유지
🔥 중요한 부분 요약
| 포인트 | 설명 |
| endTime 정렬 | 과거 작업을 빠르게 찾기 위해 |
| binary search | O(logN)으로 겹치지 않는 가장 마지막 작업 찾기 |
| dp 테이블 | 지금까지 얻은 최대 이익 저장 |
| 새 작업 추가 조건 | curProfit > dp[-1][1] 인 경우에만 추가 (항상 최대 이익만 유지) |
✨ 예시 간단 정리 (Example 1)
startTime = [1,2,3,3]
endTime = [3,4,5,6]
profit = [50,10,40,70]- 작업들 정렬: [(1,3,50), (2,4,10), (3,5,40), (3,6,70)]
- dp 시작: [(0,0)]
탐색:
- (1,3,50) → 0번까지 최대 이익 0 → 0+50=50 → 추가
- (2,4,10) → 0번까지 최대 이익 0 → 0+10=10 → 50보다 작음 → 추가 안 함
- (3,5,40) → 1번까지 최대 이익 50 → 50+40=90 → 추가
- (3,6,70) → 1번까지 최대 이익 50 → 50+70=120 → 추가
결과: 최대 이익 120
✅ 최종 요약
"끝나는 시간 순으로 정렬하고,
이진탐색으로 겹치지 않는 작업 찾고,
dp로 최대 이익을 업데이트한다."
그럼 이번엔 조금 더 "전통적인 dp 배열" 을 직접 쓰는 버전으로 깔끔하게 보여줄게.
(조금 더 명시적으로 dp[i]를 만드는 스타일이야.)
✨ 전통적인 DP 배열 버전
import bisect
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
# (start, end, profit) 묶어서 endTime 기준으로 정렬
jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
n = len(jobs)
dp = [0] * (n+1) # dp[i]: i번째 작업까지 고려했을 때 얻을 수 있는 최대 이익
# endTime만 따로 빼서 저장 (binary search용)
ends = [job[1] for job in jobs]
for i in range(1, n+1):
s, e, p = jobs[i-1]
# s보다 작거나 같은 endTime을 가진 마지막 작업 찾기
idx = bisect.bisect_right(ends, s) - 1
# dp[i] = max(직전까지의 최대 이익, 이전 non-overlap 작업까지 이익 + 현재 이익)
dp[i] = max(dp[i-1], dp[idx+1] + p)
return dp[-1]✨ 설명 (전통 dp 배열 방식)
| 단계 | 설명 |
| jobs 정렬 | 끝나는 시간 기준으로 정렬 |
| dp 배열 생성 | dp[i] = i번째까지 고려했을 때 얻을 수 있는 최대 이익 |
| ends 배열 생성 | endTime만 모아서 binary search용으로 따로 저장 |
| for문 돌면서 | - 이전 작업까지 이익 (dp[i-1]) - 겹치지 않는 가장 가까운 작업까지 이익 + 현재 profit (dp[idx+1] + p) 둘 중 큰 걸 dp[i]에 저장 |
| 최종 결과 | dp[n] (전체 작업 고려했을 때 최대 이익) |
✨ 예시 흐름 다시 보면 (Example 1)
startTime = [1,2,3,3] endTime = [3,4,5,6] profit = [50,10,40,70]
jobs 정렬:
- [(1,3,50), (2,4,10), (3,5,40), (3,6,70)]
- ends = [3,4,5,6]
dp 채우기:
| i | 작업 | 이전 최대 dp[i-1] | 선택했을 때 dp[idx+1]+profit | dp[i] |
| 1 | (1,3,50) | 0 | 0+50 | 50 |
| 2 | (2,4,10) | 50 | 0+10 | 50 |
| 3 | (3,5,40) | 50 | 50+40 | 90 |
| 4 | (3,6,70) | 90 | 50+70 | 120 |
최종 답: 120
🔥 요약 비교
방식특징
| 앞에서 보여준 버전 (dp에 (endTime, profit) 저장) | 스택처럼 dp를 간결하게 쌓는 방식 (메모리 절약, 최적화 버전) |
| 이번 전통적인 dp[i] 배열 | 모든 인덱스별로 명시적인 최대 이익 저장 (깔끔하고 이해하기 쉬움) |
✅ 최종 요약 한줄
"dp[i]는 i번째 작업까지 고려했을 때의 최대 이익을 저장한다.
겹치지 않는 마지막 작업을 이진탐색해서 연결한다."
bisect.bisect_right(ends, s)을 직접 투포인터로 구현할 수 있느냐?
→ 가능하고, 아주 간단한 이진탐색 직접구현 (binary search) 로 처리할 수 있어.
✨ 먼저 bisect_right(ends, s) 의미 복습
- ends는 endTime을 오름차순 정렬한 배열이야.
- bisect_right(ends, s)는
→ s보다 큰 값이 처음 나오는 index를 리턴해. - 그러니까, s보다 작거나 같은(end <= s) 마지막 index는
→ bisect_right(ends, s) - 1 이 되는 거야.
✨ 투포인터(이진탐색) 직접 구현 버전
def findLastNonOverlap(ends, s):
left, right = 0, len(ends) - 1
res = -1 # 기본값 (못 찾으면 -1)
while left <= right:
mid = (left + right) // 2
if ends[mid] <= s:
res = mid # 조건 만족하면 정답 후보
left = mid + 1 # 오른쪽(더 큰 값들)으로 탐색
else:
right = mid - 1 # 왼쪽(더 작은 값들)으로 탐색
return res🔥 정리
| 비교 | 설명 |
| bisect_right(ends, s) - 1 | 파이썬 내장 이진탐색 함수 사용 |
| findLastNonOverlap(ends, s) | 직접 이진탐색 구현 (투포인터 버전) |
동작 완전히 같아!
✨ 전체 코드에 적용하면
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
# 오버레핑 안되게..
# 최대 profit
jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
n = len(jobs)
dp = [0] * (n+1)
ends = [job[1] for job in jobs]
def findLastNonOverlap(ends, s):
left, right = 0, len(ends) - 1
res = -1
while left <= right:
mid = (left + right) // 2
if ends[mid] <= s:
res = mid
left = mid + 1
else:
right = mid - 1
return res
for i in range(1, n+1):
s, e, p = jobs[i-1]
"""
✅ ends 리스트 (작업들의 종료 시간들) 중에서,
✅ 현재 작업 시작 시간 s보다 작거나 같은 종료 시간을 가진
✅ 가장 마지막(오른쪽 끝) 인덱스를 찾는다.
그래서 결국
idx번째 작업은 현재 작업과 겹치지 않는 가장 마지막 작업이다.
즉, 이번 작업과 겹치지 않고 고를 수 있는 마지막 작업이다.
그런데, idx 는 0부터 시작이므로,
실제로는 dp[idx+1] 이 이번 작업과 겹치지 않고 고를 수 있는 마지막 작업의 이익 인거지.
✅ idx는 0부터 시작하는 인덱스입니다.
(즉, ends[idx]는 "현재 작업과 겹치지 않는 마지막 작업"의 위치를 가리키는 거예요.)
✅ 그런데 dp 배열은 의미가 "i번째 작업까지 고려했을 때 최대 이익" 이니까,
dp[0]은 "아무 작업도 고려 안 했을 때",
dp[1]은 "1번째 작업까지 고려한 최대 이익",
dp[2]는 "2번째 작업까지 고려한 최대 이익" 이런 식이죠.
✅ 그래서 "idx번째 작업까지 고려한 이익" 은
dp[idx+1] 에 있습니다.
"""
idx = findLastNonOverlap(ends, s) # ends 들 중 s 보다 작거나같은 가장 큰 index => 즉, 이번 작업 시작 s 와 안겹치는 작업
dp[i] = max(dp[i-1], dp[idx+1] + p) # idx 는 0부터 시작이므로, idx번째 작업까지 고려한 이익은 dp[idx+1]
return dp[-1]✅ 완벽하게 돌아간다.
- dp[i] = 1번째부터 i번째 작업까지 고려했을 때 최대 이익
- i번째 작업을 반드시 해야 한다는 뜻이 아
- dp[0] = 0 (아무 작업도 선택하지 않았을 때)
- dp[i-1]: 이번 작업을 선택 안 했을 때 최대 이익
- dp[idx+1] + p: 이번 작업을 선택했을 때 최대 이익
- idx는 "이번 작업 시작 전까지 끝나는 마지막 작업"입니다.
- dp[idx+1] 은 "idx까지 작업을 하고 얻은 최대 이익"을 의미해요.
- idx는 겹치지 않는 마지막 작업 인덱스
- dp[idx+1]: idx까지 작업한 최대 이익
- 여기에 **지금 작업의 profit p**를 더하는 거예요.
- 그런데 핵심은,
"i번째 작업을 꼭 선택하는 게 아니다" 라는 점입니다.- 이번 작업을 선택 안 하면
👉 그냥 dp[i-1] 유지 - 이번 작업을 선택 하면
👉 dp[idx+1] + 현재 profit (여기서 idx는 겹치지 않는 마지막 작업 인덱스)
- 이번 작업을 선택 안 하면
- 그래서 dp[i]를 채울 때:
-
- dp[i]의 의미는 → "i번째 작업까지 고려했을 때 얻을 수 있는 최대 이익" 입니다.
- dp[0]은 아무 작업도 고려 안 했을 때 최대 이익 (0)
- dp[1]은 첫 번째 작업까지 고려했을 때 최대 이익
- dp[2]는 두 번째 작업까지 고려했을 때 최대 이익
- ...
그래서!- idx는 "겹치지 않는 마지막 작업"의 인덱스입니다. (0-based, 0부터 시작 => 따라서, 1 더해줘야.)
- 그렇다면 idx번째 작업까지 고려했을 때 최대 이익은 dp[idx+1] 입니다.
✨ 흐름 그림으로 이해하기
- ends = [3, 4, 5, 6]
- s = 3
- findLastNonOverlap(ends, 3) 실행하면
| left | right | mid | ends[mid] | action |
| 0 | 3 | 1 | 4 | right = mid-1 |
| 0 | 0 | 0 | 3 | res = 0, left = mid+1 |
| 1 | 0 | - | - | 종료 |
→ 결과: res = 0
✅ 최종 요약 한줄
"bisect_right 대신, 투포인터(이진탐색)로 s보다 작거나 같은 마지막 endTime index를 직접 찾을 수 있다."
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
jobs = sorted(zip(startTime, endTime, profit), key=lambda x:x[1]) #end 기준 작->큰
dp = [0] * (len(jobs)+1)
dp[0] = 0 # 0번째 작업 최대 이익=0
self.ends = [j[1] for j in jobs]
def find_max_end_idx(start):
l, r = 0, len(self.ends)-1
res = -1
while l<=r:
m = (l+r)//2
if self.ends[m] <=start:
res = max(res, m)
l=m+1
else:
r = m-1
return res
for i in range(1, len(jobs)+1):
start, end, profit = jobs[i-1]
idx = find_max_end_idx(start)
dp[i] = max(dp[i-1], dp[idx+1]+profit)
return dp[len(jobs)]'LeetCode > Grind169' 카테고리의 다른 글
| 210. Course Schedule II ☆☆★★★★ DFS, BFS 둘다 풀수있게. BFS 꼭 숙지!! (0) | 2025.05.01 |
|---|---|
| 84. Largest Rectangle in Histogram ☆☆★★★ Hard (0) | 2025.04.28 |
| 146. LRU Cache ☆☆★★★ (OrderedDict 사용!!) (1) | 2025.04.28 |
| 621. Task Scheduler ☆☆★★★ (0) | 2025.04.27 |
| 310. Minimum Height Trees ☆☆★★★ (0) | 2025.04.27 |