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.