Coding interview: How do you maximize reward with non-overlapping jobs?

Prompt and use cases

Each job is (start, end, reward). Choose compatible jobs with maximum total reward; an end time equal to the next start is allowed. For (1,3,50), (3,5,40), (2,6,100), the first two jobs win with reward 90. This is a coding question testing interval ordering, predecessor lookup, and dynamic programming, regardless of implementation language.

Public algorithm material uses weighted interval/job scheduling as a dynamic-programming and interval-pattern exercise, and a public interview account also records an interval-scheduling variant. State verifiable requirements without claiming unverifiable interview frequency.

What the interviewer evaluates

• Whether you sort by end time so the last chosen job creates an ordered decision.
• Whether you define p(i), the last job ending no later than job i starts.
• Whether you compare skipping and taking the current job instead of greedily taking the largest individual reward.
• Whether binary search reduces predecessor lookup to O(log n) and whether you can reconstruct the chosen jobs.
• Whether you handle end == start, equal end times, empty input, and zero rewards.

Clarifications before answering

• Are equal end and start times compatible? This answer assumes yes: end <= start.
• Can rewards be negative? If so, explicitly allow choosing no job, with baseline 0.
• Is only the maximum reward required? This article also reconstructs the job set; omit parent data if not needed.
• Are times integers? Sorting only needs comparability; binary search does not need consecutive integers.
• Can a job be selected twice? Assume each input job is selectable at most once.
• Can start > end occur? Reject or normalize it before the recurrence; do not hide invalid data.
• How should equal intervals be ordered? Use a stable tie-break; any optimal reward is acceptable.

30-second answer framework

“I sort jobs by end and let dp[i] be the best reward from the first i jobs. For job i, binary search the last job whose end is at most start[i]; call its compatible prefix size p. The recurrence is dp[i] = max(dp[i-1], reward[i] + dp[p]): skip the job or take it with its compatible prefix. I store a choice marker and backtrack to recover the jobs. Sorting and each binary search give O(n log n) time and the arrays use O(n) space.”

Step-by-step deep answer

Step 1: Explain why a greedy rule is insufficient.

Earliest-finish-time greedy is correct when every job has equal value. With different rewards, a short low-value job can block a better combination, so local finish time or local reward is not enough.

Step 2: Define the ordered state.

After sorting, let dp[i] be the optimum for jobs 0..i-1, with dp[0] = 0. Skipping job i-1 immediately gives dp[i-1].

Step 3: Compute the predecessor.

For job i-1, find the largest j < i-1 with end[j] <= start[i-1]. Binary search the sorted end times and return its compatible prefix size p; taking the job yields reward[i-1] + dp[p].

Step 4: Write the recurrence and reconstruction.

dp[0] = 0
for i = 1..n:
  skip = dp[i - 1]
  take = reward[i - 1] + dp[p(i - 1)]
  dp[i] = max(skip, take)
  chose[i] = take > skip

Backtrack from i = n: if chose[i] is true, record job i-1 and jump to p(i-1); otherwise decrement i. Reverse the collected list. Fix a tie-break when the two rewards are equal.

Step 5: Prove correctness.

Any optimum over the first i jobs either excludes job i-1, yielding at most dp[i-1], or includes it. In the latter case every other job lies in the first p(i-1) compatible jobs, yielding at most reward[i-1] + dp[p(i-1)]. The recurrence takes the larger of these exhaustive cases. With base case dp[0] = 0, induction proves every state optimal.

Step 6: Protect implementation boundaries.

The predecessor search must use <= so adjacent jobs remain compatible. Start from zero to support negative rewards and the empty set. Reverse the backtracking result because reconstruction runs from the end.

Step 7: Analyze complexity.

Sorting costs O(n log n), and one binary search per job also costs O(n log n) in total. The dynamic-programming, predecessor, and choice arrays use O(n) space. State output size separately if it is counted.

Step 8: Identify alternatives.

If end times are small bounded integers, a time-indexed scan can avoid comparison sorting. If rewards are equal, earliest-finish greedy is enough. A limit of at most k jobs or multiple resources adds state dimensions and requires a new recurrence.

High-quality sample answer

“I sort by end time and define dp[i] as the maximum reward among the first i jobs. For each job, binary search the last predecessor with end <= start. Skipping gives dp[i-1]; taking gives reward[i] + dp[p(i)], so I keep the larger value and record the choice for backtracking. The proof partitions every optimum by whether it contains the current job; if it does, the remaining jobs must come from the compatible prefix. Sorting and binary search give O(n log n) time and O(n) auxiliary space. I test adjacent jobs, equal end times, negative rewards, complete overlap, and empty input.”

Common mistakes

• Greedy by largest reward → one job can block a higher-sum combination → compare take and skip with DP.
• Treating equal end/start as a conflict → legal adjacent jobs disappear → use end <= start.
• Sorting only by start → dp[i-1] no longer describes a stable prefix → sort by end.
• Linear predecessor scans → total time becomes O(n²) → binary-search end times.
• Initializing from the first reward → all-negative input cannot choose the empty set → set dp[0] = 0.
• Forgetting to reverse backtracking → selected jobs are returned backwards → reverse after collection.
• Leaving equal-reward ties unspecified → output changes across runs → fix a tie-break.
• Claiming one dimension handles resource limits → extra constraints are not represented → add dimensions or remodel.

Follow-up questions and responses

Follow-up 1: Why is the equal-boundary rule safe?

If one job ends exactly when another starts, they do not overlap under the stated convention. Therefore the predecessor test must include equality; changing it to < solves a different problem.

Follow-up 2: Can this always be O(n)?

With small bounded integer times, direct time scanning can be linear. In the general comparison model, sorting itself costs O(n log n), so do not promise linear time unconditionally.

Follow-up 3: How do you reconstruct the jobs?

Store a choice bit or parent pointer. From i = n, take the current job and jump to its predecessor, or decrement when skipping; reverse the collected jobs.

Follow-up 4: What if at most k jobs may be selected?

Add a count dimension such as dp[i][c] for the best reward using c jobs among the first i. Time and space increase accordingly.

Follow-up 5: What if reward depends on adjacent jobs?

The independent-reward assumption no longer holds. Include adjacency in the state or model it as a transition cost; the original recurrence is not justified without that change.

Follow-up 6: What if all jobs have the same end time?

Stable sorting is sufficient. Their predecessors are usually identical, and the recurrence still compares each candidate. For identical intervals, only the best reward matters.

Follow-up 7: When is greedy correct?

When all rewards are equal and the goal is to select the largest number of jobs, earliest-finish greedy has an exchange argument. With unequal rewards, use weighted dynamic programming.