Maximize profit from non-overlapping jobs
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given up to N = 200,000 jobs; each job i has a start time s_i, end time e_i (s_i < e_i), and reward w_i. Select a subset of non-overlapping jobs to maximize total reward. Return the maximum reward and one optimal set of job indices. Design an O(N log N) algorithm using sorting plus binary search or a balanced tree; explain how you reconstruct the chosen jobs and analyze time/space complexity. Handle duplicate start/end times, large rewards (up to 1e
9), and memory limits. Discuss alternatives (e.g., segment tree, coordinate compression) and how you would adapt the approach if jobs arrive online.
Quick Answer: This question evaluates proficiency in weighted interval scheduling, dynamic programming concepts, and the use of efficient data structures for large-scale scheduling problems, including handling duplicate times, large reward values, and memory constraints.
You are given a list of jobs, where jobs[i] = (s_i, e_i, w_i) contains a start time, end time, and reward. Two jobs are compatible if the earlier job ends at or before the later job starts.
Choose a subset of pairwise non-overlapping jobs that maximizes total reward. Return a tuple (max_reward, chosen_indices), where chosen_indices contains the original 0-based indices of one optimal subset in the order the jobs are performed.
Your algorithm should run in O(N log N) for up to 200,000 jobs. Duplicate start/end times are allowed, rewards can be large, and you should reconstruct the chosen jobs efficiently. If the input is empty, return (0, []).
For deterministic output, sort jobs by (end, start, index). During dynamic programming, if taking the current job gives the same total reward as skipping it, prefer skipping it.
In an interview explanation, be prepared to describe how you reconstruct the answer, why the complexity is O(N log N), what a segment-tree/coordinate-compression alternative looks like, and how an online version would use an ordered map or balanced tree.
Constraints
- 0 <= len(jobs) <= 200000
- 0 <= start < end <= 10^9 for every job
- 1 <= reward <= 10^9 for every job
- The total reward may exceed 32-bit signed integer range
Examples
Input: ([],)
Expected Output: (0, [])
Explanation: With no jobs, the maximum reward is 0 and the chosen set is empty.
Input: ([(1, 3, 50), (3, 5, 20), (6, 19, 100), (2, 100, 200)],)
Expected Output: (200, [3])
Explanation: Taking job 3 alone gives reward 200, which is better than chaining jobs 0, 1, and 2 for 170.
Hints
- After sorting by end time, let dp[i] be the best reward using the first i sorted jobs. For the i-th job, binary search the last job whose end time is <= its start time.
- Store both the compatible predecessor position and whether job i was taken. That lets you backtrack one optimal set of original indices. A segment tree with coordinate compression is an alternative O(N log N) approach; an online variant would need an ordered map or balanced tree keyed by end time.