Maximum Profit in Job Scheduling

Question (LC.1235)

Given n jobs with start time, end time, and profit, find the maximum profit for non-overlapping jobs.

Examples

I: 
start_time = [1, 2, 3, 3]
end_time = [3, 4, 5, 6]
profit = [50, 10, 40, 70]
O: 120 

I: 
startTime = [1, 2, 3, 4, 6]
endTime = [3, 5, 10, 6, 9]
profit = [20, 20, 100, 70, 60]
O: 150

Approach

Optimization problem

A simple exchange greedy argument is not enough because the weight is hard to swap

DP approach

Jobs with profits

dp: {1: 0, 2: 0, 3: 20, 4: 20, 5: 20, 6: 90, 9: 150, 10: 150}

Code

def jobScheduling(
  self, startTime: List[int], endTime: List[int], profit: List[int]
) -> int:
    Event = namedtuple('Event', ['time', 'is_start', 'job_id'])

    events: List[Event] = []
    dp: Dict[int, int] = {}
    for i in range(len(startTime)):
        dp[startTime[i]] = 0
        start_event = Event(startTime[i], True, i)
        events.append(start_event)
        dp[endTime[i]] = 0
        end_event = Event(endTime[i], False, i)
        events.append(end_event)

    sorted_events = sorted(events, key=lambda e: e.time)

    # init
    last_profit = 0

    # topo sort is time order
    for event in sorted_events:
        if event.is_start:
            dp[event.time] = max(dp[event.time], last_profit)
        else:
            # choose or not choose this interval
            dp[event.time] = max(
              dp[event.time], 
              dp[startTime[event.job_id]] + profit[event.job_id], 
              last_profit
            )
            last_profit = dp[event.time]

    return last_profit

Time Complexity

O(nlogn) for sorting O(n) space