NeetCode #706LC-1235Hard1-D Dynamic Programming
← Back to All Problems#706 · #1235 · Maximum Profit in Job Scheduling(规划兼职工作)
📌 Problem Statement & Constraints
Given
startTime, endTime, and profit for n jobs, choose a subset of non-overlapping jobs (a job ending at time t does not conflict with one starting at t) that maximises total profit. Return that maximum profit. Constraints: 1 <= n <= 5 * 10^4, 1 <= startTime[i] < endTime[i] <= 10^9, 1 <= profit[i] <= 10^4.💡 Core Algorithmic Approaches
- Sort the jobs by end time; let
dp[i]be the best profit using the firstijobs in that order. - For job
i, either skip it (dp[i-1]) or take it, addingprofit[i]to the best profit over jobs ending at or beforestartTime[i]. - That predecessor is found by binary searching the sorted end times for the largest value not exceeding
startTime[i]. - This yields O(n log n), far better than the naive O(n^2) transition.
💻 Benchmark Python3 Implementation
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
from bisect import bisect_right
jobs = sorted(zip(endTime, startTime, profit))
ends = [e for e, s, p in jobs]
n = len(jobs)
dp = [0] * (n + 1)
for i in range(1, n + 1):
e, s, p = jobs[i - 1]
j = bisect_right(ends, s, 0, i - 1) # jobs ending <= start
dp[i] = max(dp[i - 1], dp[j] + p)
return dp[n]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort plus one binary search per job.
💾 Space Complexity
O(n): the job list and dp.
⚠️ Interview Pitfalls & Follow-ups
- Using
bisect_left: jobs ending exactly atstartTime[i]do not conflict, sobisect_rightis correct. - Searching the whole
endsarray: the search must be limited to jobs beforei, which thehi = i - 1bound enforces. - Sorting by start time: the DP relies on end-time ordering so that predecessors form a prefix.
- Treating
end == startas a conflict: back-to-back jobs are allowed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.