How to Solve Maximum Profit in Job Scheduling

Start by sorting jobs based on their end times to enable efficient non-overlapping checks. Use a dynamic programming array to store the maximum profit achievable up to each job. For each job, perform a binary search to find the latest compatible job that ends before the current job starts, then update the DP state with the maximum of including or skipping the current job. This state transition DP approach ensures optimal selection of jobs without overlaps.

Problem Statement

You are given three arrays startTime, endTime, and profit, each of length n, representing n jobs. Job i starts at startTime[i], ends at endTime[i], and yields a profit of profit[i]. Your task is to select a subset of jobs to maximize total profit such that no two selected jobs overlap in time. If a job ends at time X, another job starting at X can be included.

Return the maximum total profit obtainable under these constraints. Optimize your approach using state transition dynamic programming, considering that naive iteration over all subsets is too slow for large n.

Examples

Example 1

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]

Output: 120

The subset chosen is the first and fourth job. Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]

Output: 150

The subset chosen is the first, fourth and fifth job. Profit obtained 150 = 20 + 70 + 60.

Example 3

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]

Output: 6

Example details omitted.

Constraints

• 1 <= startTime.length == endTime.length == profit.length <= 5 * 104
• 1 <= startTime[i] < endTime[i] <= 109
• 1 <= profit[i] <= 104

Solution Approach

Sort Jobs by End Time

First, combine the startTime, endTime, and profit arrays into a list of job tuples. Sort this list by endTime to allow efficient lookups of the last non-overlapping job for each job using binary search.

Dynamic Programming State Transition

Initialize a DP array where dp[i] represents the maximum profit including jobs up to index i. For each job, perform a binary search to find the latest job that ends before the current job starts. Update dp[i] as the maximum of dp[i-1] (skipping current job) and dp[lastCompatible] + profit[i] (including current job).

Binary Search for Compatible Jobs

Use binary search to efficiently locate the last job that finishes before the current job starts. This avoids linear scans and maintains the overall time complexity near O(n log n). Each DP update then considers only valid non-overlapping sequences.

Complexity Analysis

Time complexity is O(n log n) due to sorting and binary search for each job. Space complexity is O(n) for storing DP states and the combined job list.

What Interviewers Usually Probe

• Expect sorting by end times before DP.
• Look for correct DP state definition to store maximum profit up to each job.
• Binary search for previous compatible job is crucial for efficiency.

Common Pitfalls or Variants

Common pitfalls

• Forgetting that a job ending at X can allow a new job starting at X.
• Performing linear search instead of binary search, increasing runtime.
• Incorrectly updating DP array, not considering the maximum between including or skipping a job.

Follow-up variants

• Allow jobs with equal start and end times and handle them in DP updates.
• Find the maximum number of jobs instead of profit using a similar DP approach.
• Add a constraint on maximum total duration and adapt the DP to track both profit and duration.

How GhostInterview Helps

• Automatically structures DP state transitions and binary search steps for maximum profit in job scheduling.
• Highlights failure modes, such as overlapping jobs and off-by-one indexing in DP updates.
• Provides example-driven verification, helping users trace why specific job combinations yield the optimal solution.

Topic Pages

• Array
• Binary Search
• Dynamic Programming
• Sorting

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main approach to solve Maximum Profit in Job Scheduling?

Use state transition dynamic programming with jobs sorted by end time and binary search to find the latest non-overlapping job for each step.

Can jobs that end and start at the same time be scheduled together?

Yes, a job ending at time X allows inclusion of another job starting at X without overlapping.

What is the time complexity for this DP with binary search approach?

Sorting takes O(n log n) and each job uses O(log n) binary search, resulting in O(n log n) overall time complexity.

How does GhostInterview help with edge cases?

It guides users to check DP updates for overlapping jobs and ensures correct maximum profit calculations on examples.

Are there common mistakes to avoid in this problem?

Yes, forgetting inclusive end-start scheduling, not using binary search, or miscalculating DP states are frequent errors.