1235. Maximum Profit in Job Scheduling
hardAsked at CitadelThis problem is a weighted interval scheduling problem — find the maximum-profit subset of non-overlapping intervals. At Citadel, structurally identical problems appear in trade-off analysis: selecting the highest-value set of non-overlapping trading windows subject to latency budgets. It demands DP on sorted intervals with binary search, testing both algorithmic depth and implementation rigor.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Citadel loops.
- Glassdoor (2025-10)— Citadel SWE hard-round candidates cite Maximum Profit in Job Scheduling as a senior-level problem combining DP and binary search.
- Blind (2025-08)— Citadel SWE threads identify this problem as a hallmark of the 'sort + DP + binary search' pattern category that Citadel tests in final rounds.
Problem
We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit[i]. You're given the startTime, endTime, and profit arrays. Return the maximum profit you can take such that there are no two jobs in the subset with overlapping time ranges. If you choose a job that ends at time X, you will be able to start another job that starts at time X.
Constraints
1 <= startTime.length == endTime.length == profit.length <= 5 * 10^41 <= startTime[i] < endTime[i] <= 10^91 <= profit[i] <= 10^4
Examples
Example 1
startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]120Explanation: Schedule jobs 0 and 3 (non-overlapping): profit 50 + 70 = 120.
Example 2
startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,200,200]200Explanation: Best is job 3 (start=4, end=6, profit=200) alone.
Example 3
startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]6Explanation: Only one job can be taken; job 1 (profit=6) is optimal.
Approaches
1. Sort by end time + DP + binary search
Sort jobs by end time. Define dp[i] = max profit considering the first i jobs. For job i, either skip it (dp[i] = dp[i-1]) or take it (dp[i] = profit[i] + dp[j] where j is the latest job that ends ≤ start[i], found via binary search).
- Time
- O(n log n)
- Space
- O(n)
function jobScheduling(startTime, endTime, profit) {
const n = startTime.length;
// Zip into jobs and sort by end time
const jobs = [];
for (let i = 0; i < n; i++) {
jobs.push([endTime[i], startTime[i], profit[i]]);
}
jobs.sort((a, b) => a[0] - b[0]);
// dp[i] = max profit using jobs[0..i-1]
// endTimes[i] = end time of jobs[i-1] (for binary search)
const dp = [0]; // dp[0] = 0 (no jobs taken)
const endTimes = [0]; // sentinel
for (const [end, start, p] of jobs) {
// Binary search: find the latest job that ends <= start
let lo = 0, hi = dp.length - 1;
while (lo < hi) {
const mid = (lo + hi + 1) >> 1;
if (endTimes[mid] <= start) lo = mid;
else hi = mid - 1;
}
// Option 1: skip this job. Option 2: take this job.
const profitWithJob = dp[lo] + p;
const profitWithoutJob = dp[dp.length - 1];
dp.push(Math.max(profitWithJob, profitWithoutJob));
endTimes.push(end);
}
return dp[dp.length - 1];
}Tradeoff: O(n log n) for sorting and binary search per job. O(n) DP array. This is the canonical approach. The binary search finds the 'previous non-overlapping job' in O(log n) — the key insight that reduces O(n²) DP to O(n log n).
Citadel-specific tips
State the DP framing before coding: 'This is weighted interval scheduling — a classic DP on sorted intervals. I sort by end time, define dp[i] as the maximum profit achievable using the first i jobs, and for each job I binary-search for the last non-overlapping job.' Draw a timeline: jobs sorted by end time, and for each new job, a binary search on the endTimes array. Citadel interviewers will ask: 'What if you had constraints on the maximum number of jobs?' — that extends the DP to dp[i][k] = max profit using i jobs and taking at most k of them, a 2D DP problem.
Common mistakes
- Not sorting by end time before the DP — sorting by start time leads to incorrect binary search results.
- Binary searching for jobs that end < start instead of <= start — the problem states you can start a job at time X if the previous ends at time X.
- Using dp[i] to represent individual jobs instead of prefixes — you need a prefix-max DP, not per-job DP.
- Forgetting the sentinel dp[0] = 0 and endTimes[0] = 0 — the base case (no jobs, no profit) must be included so binary search can return 0 when no prior job fits.
Follow-up questions
An interviewer at Citadel may pivot to one of these next:
- If you can take at most k non-overlapping jobs, what changes? (2D DP: dp[i][j] = max profit using first i jobs, taking exactly j.)
- Weighted Job Scheduling with deadlines — add a deadline constraint where each job must complete by a certain time.
- How would you solve this if new jobs arrive as a stream (online setting)?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why sort by end time rather than start time?
The DP transition is: 'take or skip this job.' Taking it means adding its profit to the max profit of all non-overlapping jobs before it. 'Before it' is defined by end time — you need to find the latest job that ends ≤ this job's start. This requires the jobs and their end times to be sorted.
What does the binary search return when no prior job fits?
The sentinel endTimes[0] = 0 ensures lo = 0 when no job ends ≤ start. dp[0] = 0, so the profit contribution from prior jobs is 0 — correct base case.
Is there an O(n) solution?
No — sorting requires O(n log n) and the binary search per job is O(log n). O(n log n) is optimal for this problem class (weighted interval scheduling has been proven to require at least this much work under comparison model).
Practice these live with InterviewChamp.AI
Drill Maximum Profit in Job Scheduling and other Citadel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →