⚡Flashcard Drill➔
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

  1. Sort the jobs by end time; let dp[i] be the best profit using the first i jobs in that order.
  2. For job i, either skip it (dp[i-1]) or take it, adding profit[i] to the best profit over jobs ending at or before startTime[i].
  3. That predecessor is found by binary searching the sorted end times for the largest value not exceeding startTime[i].
  4. 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 at startTime[i] do not conflict, so bisect_right is correct.
  • Searching the whole ends array: the search must be limited to jobs before i, which the hi = i - 1 bound enforces.
  • Sorting by start time: the DP relies on end-time ordering so that predecessors form a prefix.
  • Treating end == start as 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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems