Maximum Profit in Job Scheduling
Hard · Dynamic Programming · about 30 minutes
Asked at Airbnb, DoorDash, Google, Amazon, Microsoft, Bloomberg, Toast.
There are n jobs: job i runs from startTime[i] to endTime[i] and earns profit[i]. Choose a set of non-overlapping jobs to maximize the total profit. A job ending at time X doesn't overlap one starting at X. Return the maximum profit.