Maximum Profit in Job Scheduling

The problem description can be found in LeetCode.

Approach

An easy way to think about this problem would be reason on how we should select or discard a certain job.

What if we try every possibility?

We can either select the first job or discard it. Then, for both choices, we can again select the second job or discard it.

This decision tree and a possible repeating work in checking this options suggest to apply Dynamic Programming.

However, we need an efficient way for selecting the next job that we might select or discard. Usually, for these kind of problems, sorting the input is highly recommended, since any other brute force approach would have surely a higher complexity compared to $O(nlog(n))$.

Again, sorting the input suggests that Binary Search might be used. In fact, in order to select the next job, we can use it to quickly find it.

Solution

import bisect
from typing import Dict, List


class Solution:
    def jobScheduling(
        self, startTimes: List[int], endTimes: List[int], profits: List[int]
    ) -> int:
        def dfs(i: int, memo: Dict[int, int]) -> int:
            if i >= len(startTimes):
                return 0
            if i in memo:
                return memo[i]

            next_pos = bisect.bisect_left(startTimes, endTimes[i])
            profit = max(
                dfs(i + 1, memo),
                profits[i] + dfs(next_pos, memo),
            )

            memo[i] = profit

            return memo[i]

        # sort the lists based on the `startTimes` one
        combined = list(zip(startTimes, endTimes, profits))
        sorted_combined = sorted(combined, key=lambda lst: lst[0])
        startTimes = [v[0] for v in sorted_combined]
        endTimes = [v[1] for v in sorted_combined]
        profits = [v[2] for v in sorted_combined]

        return dfs(0, {})

Complexity

• Time: $O(nlog(n))$
• Space: $O(n)$

Where $n$ is the size of the three input lists.