1235. Maximum Profit in Job Scheduling - Explanation

Description

You are given n jobs described with three arrays: startTime, endTime, and profit. The i--th job starts at startTime[i], ends at endTime[i], and yields a profit of profit[i].

Return the maximum profit achievable by selecting a subset of jobs such that no two selected jobs overlap in their time ranges.

Note: If a job ends at time X, you are allowed to start another job that begins exactly at time X.

Example 1:

Input: startTime = [4,2,4,8,2], endTime = [5,5,5,10,8], profit = [1,2,8,10,4]

Output: 18

Explanation: The subset to choose to get maximum profit is the third and fourth job (8 + 10 = 18).

Example 2:

Input: startTime = [2,3,4,5,7], endTime = [4,6,11,7,10], profit = [100,100,180,150,140]

Output: 390

Explanation: The subset to choose to get maximum profit is the first, second and fifth job (100 + 140 + 150 = 390).

Constraints:

1 <= startTime.length == endTime.length == profit.length <= 50,000
1 <= startTime[i] < endTime[i] <= 1,000,000,000
1 <= profit[i] <= 10,000

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Dynamic Programming (Memoization) - Using recursion with caching to avoid recomputing overlapping subproblems
Sorting - Sorting jobs by start time to enable efficient forward traversal
Binary Search - Finding the next non-overlapping job in O(log n) time instead of linear scan
Interval Scheduling - Understanding how to handle overlapping intervals and make optimal skip/take decisions

1. Dynamic Programming (Top-Down)

Intuition

This is a classic interval scheduling problem. For each job, we have two choices: skip it or take it. If we take a job, we earn its profit but must skip all overlapping jobs. By sorting jobs by start time and using memoization, we can efficiently explore all valid schedules.

Algorithm

Combine start times, end times, and profits into intervals and sort by start time.
Use recursion with memoization starting from index 0.
At each index i, either skip the job or take it.
If taking the job, find the next non-overlapping job by scanning forward.
Return the maximum profit achievable.

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        intervals = sorted(zip(startTime, endTime, profit))
        cache = {}

        def dfs(i):
            if i == len(intervals):
                return 0
            if i in cache:
                return cache[i]

            # don't include
            res = dfs(i + 1)

            # include
            j = i + 1
            while j < len(intervals):
                if intervals[i][1] <= intervals[j][0]:
                    break
                j += 1

            cache[i] = res = max(res, intervals[i][2] + dfs(j))
            return res

        return dfs(0)

public class Solution {
    private int[][] intervals;
    private int[] cache;

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        intervals = new int[n][3];
        cache = new int[n];
        Arrays.fill(cache, -1);

        for (int i = 0; i < n; i++) {
            intervals[i] = new int[]{startTime[i], endTime[i], profit[i]};
        }
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        return dfs(0);
    }

    private int dfs(int i) {
        if (i == intervals.length) {
            return 0;
        }
        if (cache[i] != -1) {
            return cache[i];
        }

        // Don't include
        int res = dfs(i + 1);

        // Include
        int j = i + 1;
        while (j < intervals.length && intervals[i][1] > intervals[j][0]) {
            j++;
        }

        return cache[i] = Math.max(res, intervals[i][2] + dfs(j));
    }
}

class Solution {
public:
    vector<vector<int>> intervals;
    vector<int> cache;

    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        intervals.resize(n, vector<int>(3));
        cache.assign(n, -1);

        for (int i = 0; i < n; i++) {
            intervals[i] = {startTime[i], endTime[i], profit[i]};
        }
        sort(intervals.begin(), intervals.end());

        return dfs(0);
    }

private:
    int dfs(int i) {
        if (i == intervals.size()) {
            return 0;
        }
        if (cache[i] != -1) {
            return cache[i];
        }

        // Don't include
        int res = dfs(i + 1);

        // Include
        int j = i + 1;
        while (j < intervals.size() && intervals[i][1] > intervals[j][0]) {
            j++;
        }

        return cache[i] = max(res, intervals[i][2] + dfs(j));
    }
};

class Solution {
    /**
     * @param {number[]} startTime
     * @param {number[]} endTime
     * @param {number[]} profit
     * @return {number}
     */
    jobScheduling(startTime, endTime, profit) {
        let n = startTime.length;
        let intervals = new Array(n)
            .fill(null)
            .map((_, i) => [startTime[i], endTime[i], profit[i]]);
        intervals.sort((a, b) => a[0] - b[0]);

        let cache = new Array(n).fill(-1);

        const dfs = (i) => {
            if (i === n) {
                return 0;
            }
            if (cache[i] !== -1) {
                return cache[i];
            }

            // Don't include
            let res = dfs(i + 1);

            // Include
            let j = i + 1;
            while (j < n && intervals[i][1] > intervals[j][0]) {
                j++;
            }

            return (cache[i] = Math.max(res, intervals[i][2] + dfs(j)));
        };

        return dfs(0);
    }
}

public class Solution {
    public int JobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.Length;
        var intervals = new List<(int start, int end, int profit)>();

        for (int i = 0; i < n; i++) {
            intervals.Add((startTime[i], endTime[i], profit[i]));
        }

        intervals.Sort((a, b) => a.start.CompareTo(b.start));
        Dictionary<int, int> cache = new();

        int Dfs(int i) {
            if (i == n) return 0;
            if (cache.ContainsKey(i)) return cache[i];

            // Option 1: don't include
            int res = Dfs(i + 1);

            // Option 2: include current job
            int j = i + 1;
            while (j < n && intervals[j].start < intervals[i].end) {
                j++;
            }

            res = Math.Max(res, intervals[i].profit + Dfs(j));
            cache[i] = res;
            return res;
        }

        return Dfs(0);
    }
}

func jobScheduling(startTime []int, endTime []int, profit []int) int {
    n := len(startTime)
    intervals := make([][3]int, n)
    for i := 0; i < n; i++ {
        intervals[i] = [3]int{startTime[i], endTime[i], profit[i]}
    }
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    cache := make(map[int]int)

    var dfs func(i int) int
    dfs = func(i int) int {
        if i == n {
            return 0
        }
        if val, ok := cache[i]; ok {
            return val
        }

        res := dfs(i + 1)

        j := i + 1
        for j < n && intervals[i][1] > intervals[j][0] {
            j++
        }

        res = max(res, intervals[i][2]+dfs(j))
        cache[i] = res
        return res
    }

    return dfs(0)
}

class Solution {
    fun jobScheduling(startTime: IntArray, endTime: IntArray, profit: IntArray): Int {
        val n = startTime.size
        val intervals = Array(n) { i -> intArrayOf(startTime[i], endTime[i], profit[i]) }
        intervals.sortBy { it[0] }

        val cache = IntArray(n) { -1 }

        fun dfs(i: Int): Int {
            if (i == n) return 0
            if (cache[i] != -1) return cache[i]

            var res = dfs(i + 1)

            var j = i + 1
            while (j < n && intervals[i][1] > intervals[j][0]) {
                j++
            }

            res = maxOf(res, intervals[i][2] + dfs(j))
            cache[i] = res
            return res
        }

        return dfs(0)
    }
}

class Solution {
    func jobScheduling(_ startTime: [Int], _ endTime: [Int], _ profit: [Int]) -> Int {
        let n = startTime.count
        var intervals = (0..<n).map { (startTime[$0], endTime[$0], profit[$0]) }
        intervals.sort { $0.0 < $1.0 }

        var cache = [Int: Int]()

        func dfs(_ i: Int) -> Int {
            if i == n { return 0 }
            if let val = cache[i] { return val }

            var res = dfs(i + 1)

            var j = i + 1
            while j < n && intervals[i].1 > intervals[j].0 {
                j += 1
            }

            res = max(res, intervals[i].2 + dfs(j))
            cache[i] = res
            return res
        }

        return dfs(0)
    }
}

impl Solution {
    pub fn job_scheduling(start_time: Vec<i32>, end_time: Vec<i32>, profit: Vec<i32>) -> i32 {
        let n = start_time.len();
        let mut intervals: Vec<(i32, i32, i32)> = (0..n)
            .map(|i| (start_time[i], end_time[i], profit[i]))
            .collect();
        intervals.sort();

        let mut cache = vec![-1; n];

        fn dfs(i: usize, intervals: &[(i32, i32, i32)], cache: &mut Vec<i32>) -> i32 {
            if i == intervals.len() {
                return 0;
            }
            if cache[i] != -1 {
                return cache[i];
            }
            let mut res = dfs(i + 1, intervals, cache);
            let mut j = i + 1;
            while j < intervals.len() && intervals[i].1 > intervals[j].0 {
                j += 1;
            }
            res = res.max(intervals[i].2 + dfs(j, intervals, cache));
            cache[i] = res;
            res
        }

        dfs(0, &intervals, &mut cache)
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Dynamic Programming (Top-Down) + Binary Search

Intuition

The linear scan to find the next non-overlapping job can be optimized using binary search. Since jobs are sorted by start time, we can binary search for the first job whose start time is at least the current job's end time.

Algorithm

Sort intervals by start time.
Use recursion with memoization.
At each index, either skip the job or take it.
When taking a job, use binary search to find the next non-overlapping job.
Return the maximum profit.

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        intervals = sorted(zip(startTime, endTime, profit))
        cache = {}

        def dfs(i):
            if i == len(intervals):
                return 0
            if i in cache:
                return cache[i]

            # don't include
            res = dfs(i + 1)

            # include
            j = bisect.bisect(intervals, (intervals[i][1], -1, -1))
            cache[i] = res = max(res, intervals[i][2] + dfs(j))
            return res

        return dfs(0)

public class Solution {
    private int[][] intervals;
    private int[] cache;

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        intervals = new int[n][3];
        cache = new int[n];
        Arrays.fill(cache, -1);

        for (int i = 0; i < n; i++) {
            intervals[i] = new int[]{startTime[i], endTime[i], profit[i]};
        }
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        return dfs(0);
    }

    private int dfs(int i) {
        if (i == intervals.length) {
            return 0;
        }
        if (cache[i] != -1) {
            return cache[i];
        }

        int res = dfs(i + 1);

        int left = i + 1, right = intervals.length, j = intervals.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (intervals[mid][0] >= intervals[i][1]) {
                j = mid;
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return cache[i] = Math.max(res, intervals[i][2] + dfs(j));
    }
}

class Solution {
public:
    vector<vector<int>> intervals;
    vector<int> cache;

    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        intervals.resize(n, vector<int>(3));
        cache.assign(n, -1);

        for (int i = 0; i < n; i++) {
            intervals[i] = {startTime[i], endTime[i], profit[i]};
        }
        sort(intervals.begin(), intervals.end());

        return dfs(0);
    }

private:
    int dfs(int i) {
        if (i == intervals.size()) {
            return 0;
        }
        if (cache[i] != -1) {
            return cache[i];
        }

        int res = dfs(i + 1);

        int left = i + 1, right = intervals.size(), j = intervals.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (intervals[mid][0] >= intervals[i][1]) {
                j = mid;
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return cache[i] = max(res, intervals[i][2] + dfs(j));
    }
};

class Solution {
    /**
     * @param {number[]} startTime
     * @param {number[]} endTime
     * @param {number[]} profit
     * @return {number}
     */
    jobScheduling(startTime, endTime, profit) {
        let n = startTime.length;
        let intervals = new Array(n)
            .fill(null)
            .map((_, i) => [startTime[i], endTime[i], profit[i]]);
        intervals.sort((a, b) => a[0] - b[0]);

        let cache = new Array(n).fill(-1);

        const dfs = (i) => {
            if (i === n) {
                return 0;
            }
            if (cache[i] !== -1) {
                return cache[i];
            }

            let res = dfs(i + 1);

            let left = i + 1,
                right = n,
                j = n;
            while (left < right) {
                let mid = Math.floor((left + right) / 2);
                if (intervals[mid][0] >= intervals[i][1]) {
                    j = mid;
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }

            return (cache[i] = Math.max(res, intervals[i][2] + dfs(j)));
        };

        return dfs(0);
    }
}

public class Solution {
    private int[][] intervals;
    private int[] cache;

    public int JobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.Length;
        intervals = new int[n][];
        cache = new int[n];
        Array.Fill(cache, -1);

        for (int i = 0; i < n; i++) {
            intervals[i] = new int[] { startTime[i], endTime[i], profit[i] };
        }

        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
        return Dfs(0);
    }

    private int Dfs(int i) {
        if (i == intervals.Length) return 0;
        if (cache[i] != -1) return cache[i];

        int res = Dfs(i + 1);

        int left = i + 1, right = intervals.Length, j = intervals.Length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (intervals[mid][0] >= intervals[i][1]) {
                j = mid;
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        cache[i] = Math.Max(res, intervals[i][2] + Dfs(j));
        return cache[i];
    }
}

func jobScheduling(startTime []int, endTime []int, profit []int) int {
    n := len(startTime)
    intervals := make([][3]int, n)
    for i := 0; i < n; i++ {
        intervals[i] = [3]int{startTime[i], endTime[i], profit[i]}
    }
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    cache := make([]int, n)
    for i := range cache {
        cache[i] = -1
    }

    var dfs func(i int) int
    dfs = func(i int) int {
        if i == n {
            return 0
        }
        if cache[i] != -1 {
            return cache[i]
        }

        res := dfs(i + 1)

        left, right, j := i+1, n, n
        for left < right {
            mid := left + (right-left)/2
            if intervals[mid][0] >= intervals[i][1] {
                j = mid
                right = mid
            } else {
                left = mid + 1
            }
        }

        cache[i] = max(res, intervals[i][2]+dfs(j))
        return cache[i]
    }

    return dfs(0)
}

class Solution {
    fun jobScheduling(startTime: IntArray, endTime: IntArray, profit: IntArray): Int {
        val n = startTime.size
        val intervals = Array(n) { i -> intArrayOf(startTime[i], endTime[i], profit[i]) }
        intervals.sortBy { it[0] }

        val cache = IntArray(n) { -1 }

        fun dfs(i: Int): Int {
            if (i == n) return 0
            if (cache[i] != -1) return cache[i]

            var res = dfs(i + 1)

            var left = i + 1
            var right = n
            var j = n
            while (left < right) {
                val mid = left + (right - left) / 2
                if (intervals[mid][0] >= intervals[i][1]) {
                    j = mid
                    right = mid
                } else {
                    left = mid + 1
                }
            }

            cache[i] = maxOf(res, intervals[i][2] + dfs(j))
            return cache[i]
        }

        return dfs(0)
    }
}

class Solution {
    func jobScheduling(_ startTime: [Int], _ endTime: [Int], _ profit: [Int]) -> Int {
        let n = startTime.count
        var intervals = (0..<n).map { (startTime[$0], endTime[$0], profit[$0]) }
        intervals.sort { $0.0 < $1.0 }

        var cache = [Int](repeating: -1, count: n)

        func dfs(_ i: Int) -> Int {
            if i == n { return 0 }
            if cache[i] != -1 { return cache[i] }

            var res = dfs(i + 1)

            var left = i + 1, right = n, j = n
            while left < right {
                let mid = left + (right - left) / 2
                if intervals[mid].0 >= intervals[i].1 {
                    j = mid
                    right = mid
                } else {
                    left = mid + 1
                }
            }

            cache[i] = max(res, intervals[i].2 + dfs(j))
            return cache[i]
        }

        return dfs(0)
    }
}

impl Solution {
    pub fn job_scheduling(start_time: Vec<i32>, end_time: Vec<i32>, profit: Vec<i32>) -> i32 {
        let n = start_time.len();
        let mut intervals: Vec<(i32, i32, i32)> = (0..n)
            .map(|i| (start_time[i], end_time[i], profit[i]))
            .collect();
        intervals.sort();

        let mut cache = vec![-1; n];

        fn dfs(i: usize, intervals: &[(i32, i32, i32)], cache: &mut Vec<i32>) -> i32 {
            let n = intervals.len();
            if i == n {
                return 0;
            }
            if cache[i] != -1 {
                return cache[i];
            }
            let mut res = dfs(i + 1, intervals, cache);

            let mut left = i + 1;
            let mut right = n;
            let mut j = n;
            while left < right {
                let mid = left + (right - left) / 2;
                if intervals[mid].0 >= intervals[i].1 {
                    j = mid;
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }

            res = res.max(intervals[i].2 + dfs(j, intervals, cache));
            cache[i] = res;
            res
        }

        dfs(0, &intervals, &mut cache)
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Dynamic Programming (Top-Down) + Binary Search (Optimal)

Intuition

Instead of creating new interval objects, we can sort indices by start time and work with the original arrays. This reduces memory allocations while maintaining the same algorithmic approach.

Algorithm

Create an index array and sort it by start time of the corresponding jobs.
Use recursion with memoization on the sorted indices.
At each position, either skip the current job or take it.
Binary search for the next non-overlapping job using the original arrays.
Return the maximum profit.

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        n = len(startTime)
        index = list(range(n))
        index.sort(key=lambda i: startTime[i])

        cache = [-1] * n

        def dfs(i):
            if i == n:
                return 0
            if cache[i] != -1:
                return cache[i]

            res = dfs(i + 1)

            left, right, j = i + 1, n, n
            while left < right:
                mid = (left + right) // 2
                if startTime[index[mid]] >= endTime[index[i]]:
                    j = mid
                    right = mid
                else:
                    left = mid + 1

            cache[i] = res = max(res, profit[index[i]] + dfs(j))
            return res

        return dfs(0)

public class Solution {
    private int[] startTime, endTime, profit, cache;
    private Integer[] index;
    private int n;

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        this.n = startTime.length;
        this.startTime = startTime;
        this.endTime = endTime;
        this.profit = profit;
        this.index = new Integer[n];
        this.cache = new int[n];
        Arrays.fill(cache, -1);

        for (int i = 0; i < n; i++) {
            index[i] = i;
        }
        Arrays.sort(index, Comparator.comparingInt(i -> startTime[i]));

        return dfs(0);
    }

    private int dfs(int i) {
        if (i == n) {
            return 0;
        }
        if (cache[i] != -1) {
            return cache[i];
        }

        int res = dfs(i + 1);

        int left = i + 1, right = n, j = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (startTime[index[mid]] >= endTime[index[i]]) {
                j = mid;
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return cache[i] = Math.max(res, profit[index[i]] + dfs(j));
    }
}

class Solution {
public:
    vector<int> startTime, endTime, profit, index, cache;
    int n;

    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        this->n = startTime.size();
        this->startTime = startTime;
        this->endTime = endTime;
        this->profit = profit;
        this->index.resize(n);
        this->cache.assign(n, -1);

        for (int i = 0; i < n; i++) {
            index[i] = i;
        }
        sort(index.begin(), index.end(), [&](int i, int j) {
            return startTime[i] < startTime[j];
        });

        return dfs(0);
    }

private:
    int dfs(int i) {
        if (i == n) {
            return 0;
        }
        if (cache[i] != -1) {
            return cache[i];
        }

        int res = dfs(i + 1);

        int left = i + 1, right = n, j = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (startTime[index[mid]] >= endTime[index[i]]) {
                j = mid;
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return cache[i] = max(res, profit[index[i]] + dfs(j));
    }
};

class Solution {
    /**
     * @param {number[]} startTime
     * @param {number[]} endTime
     * @param {number[]} profit
     * @return {number}
     */
    jobScheduling(startTime, endTime, profit) {
        let n = startTime.length;
        let index = Array.from({ length: n }, (_, i) => i);
        index.sort((a, b) => startTime[a] - startTime[b]);

        let cache = new Array(n).fill(-1);

        const dfs = (i) => {
            if (i === n) {
                return 0;
            }
            if (cache[i] !== -1) {
                return cache[i];
            }

            let res = dfs(i + 1);

            let left = i + 1,
                right = n,
                j = n;
            while (left < right) {
                let mid = Math.floor((left + right) / 2);
                if (startTime[index[mid]] >= endTime[index[i]]) {
                    j = mid;
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }

            return (cache[i] = Math.max(res, profit[index[i]] + dfs(j)));
        };

        return dfs(0);
    }
}

public class Solution {
    private int[] startTime, endTime, profit, cache;
    private int[] index;
    private int n;

    public int JobScheduling(int[] startTime, int[] endTime, int[] profit) {
        this.n = startTime.Length;
        this.startTime = startTime;
        this.endTime = endTime;
        this.profit = profit;
        this.index = new int[n];
        this.cache = new int[n];
        Array.Fill(cache, -1);

        for (int i = 0; i < n; i++) {
            index[i] = i;
        }

        Array.Sort(index, (a, b) => startTime[a].CompareTo(startTime[b]));

        return Dfs(0);
    }

    private int Dfs(int i) {
        if (i == n) return 0;
        if (cache[i] != -1) return cache[i];

        int res = Dfs(i + 1);

        int left = i + 1, right = n, j = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (startTime[index[mid]] >= endTime[index[i]]) {
                j = mid;
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return cache[i] = Math.Max(res, profit[index[i]] + Dfs(j));
    }
}

func jobScheduling(startTime []int, endTime []int, profit []int) int {
    n := len(startTime)
    index := make([]int, n)
    for i := 0; i < n; i++ {
        index[i] = i
    }
    sort.Slice(index, func(i, j int) bool {
        return startTime[index[i]] < startTime[index[j]]
    })

    cache := make([]int, n)
    for i := range cache {
        cache[i] = -1
    }

    var dfs func(i int) int
    dfs = func(i int) int {
        if i == n {
            return 0
        }
        if cache[i] != -1 {
            return cache[i]
        }

        res := dfs(i + 1)

        left, right, j := i+1, n, n
        for left < right {
            mid := left + (right-left)/2
            if startTime[index[mid]] >= endTime[index[i]] {
                j = mid
                right = mid
            } else {
                left = mid + 1
            }
        }

        cache[i] = max(res, profit[index[i]]+dfs(j))
        return cache[i]
    }

    return dfs(0)
}

class Solution {
    fun jobScheduling(startTime: IntArray, endTime: IntArray, profit: IntArray): Int {
        val n = startTime.size
        val index = (0 until n).sortedBy { startTime[it] }.toIntArray()
        val cache = IntArray(n) { -1 }

        fun dfs(i: Int): Int {
            if (i == n) return 0
            if (cache[i] != -1) return cache[i]

            var res = dfs(i + 1)

            var left = i + 1
            var right = n
            var j = n
            while (left < right) {
                val mid = left + (right - left) / 2
                if (startTime[index[mid]] >= endTime[index[i]]) {
                    j = mid
                    right = mid
                } else {
                    left = mid + 1
                }
            }

            cache[i] = maxOf(res, profit[index[i]] + dfs(j))
            return cache[i]
        }

        return dfs(0)
    }
}

class Solution {
    func jobScheduling(_ startTime: [Int], _ endTime: [Int], _ profit: [Int]) -> Int {
        let n = startTime.count
        let index = (0..<n).sorted { startTime[$0] < startTime[$1] }
        var cache = [Int](repeating: -1, count: n)

        func dfs(_ i: Int) -> Int {
            if i == n { return 0 }
            if cache[i] != -1 { return cache[i] }

            var res = dfs(i + 1)

            var left = i + 1, right = n, j = n
            while left < right {
                let mid = left + (right - left) / 2
                if startTime[index[mid]] >= endTime[index[i]] {
                    j = mid
                    right = mid
                } else {
                    left = mid + 1
                }
            }

            cache[i] = max(res, profit[index[i]] + dfs(j))
            return cache[i]
        }

        return dfs(0)
    }
}

impl Solution {
    pub fn job_scheduling(start_time: Vec<i32>, end_time: Vec<i32>, profit: Vec<i32>) -> i32 {
        let n = start_time.len();
        let mut index: Vec<usize> = (0..n).collect();
        index.sort_by_key(|&i| start_time[i]);

        let mut cache = vec![-1i32; n];

        fn dfs(
            i: usize, index: &[usize],
            start_time: &[i32], end_time: &[i32], profit: &[i32],
            cache: &mut Vec<i32>,
        ) -> i32 {
            let n = index.len();
            if i == n {
                return 0;
            }
            if cache[i] != -1 {
                return cache[i];
            }
            let mut res = dfs(i + 1, index, start_time, end_time, profit, cache);

            let mut left = i + 1;
            let mut right = n;
            let mut j = n;
            while left < right {
                let mid = left + (right - left) / 2;
                if start_time[index[mid]] >= end_time[index[i]] {
                    j = mid;
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }

            res = res.max(profit[index[i]] + dfs(j, index, start_time, end_time, profit, cache));
            cache[i] = res;
            res
        }

        dfs(0, &index, &start_time, &end_time, &profit, &mut cache)
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

4. Dynamic Programming (Bottom-Up) + Binary Search

Intuition

We can convert the top-down approach to bottom-up by iterating from the last job to the first. At each position, we compute the maximum profit considering all jobs from that point onwards. This eliminates recursion overhead.

Algorithm

Sort indices by start time.
Create a DP array where dp[i] represents the maximum profit starting from job i.
Iterate from n-1 down to 0.
For each job, use binary search to find the next non-overlapping job.
dp[i] = max(dp[i+1], profit[i] + dp[j]) where j is the next non-overlapping job.
Return dp[0].

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        n = len(startTime)
        index = list(range(n))
        index.sort(key=lambda i: startTime[i])

        dp = [0] * (n + 1)

        for i in range(n - 1, -1, -1):
            left, right, j = i + 1, n, n
            while left < right:
                mid = (left + right) // 2
                if startTime[index[mid]] >= endTime[index[i]]:
                    j = mid
                    right = mid
                else:
                    left = mid + 1

            dp[i] = max(dp[i + 1], profit[index[i]] + dp[j])

        return dp[0]

public class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        Integer[] index = new Integer[n];
        for (int i = 0; i < n; i++) index[i] = i;
        Arrays.sort(index, Comparator.comparingInt(i -> startTime[i]));

        int[] dp = new int[n + 1];

        for (int i = n - 1; i >= 0; i--) {
            int left = i + 1, right = n, j = n;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (startTime[index[mid]] >= endTime[index[i]]) {
                    j = mid;
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            dp[i] = Math.max(dp[i + 1], profit[index[i]] + dp[j]);
        }

        return dp[0];
    }
}

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<int> index(n), dp(n + 1, 0);
        for (int i = 0; i < n; i++) index[i] = i;
        sort(index.begin(), index.end(), [&](int i, int j) {
            return startTime[i] < startTime[j];
        });

        for (int i = n - 1; i >= 0; i--) {
            int left = i + 1, right = n, j = n;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (startTime[index[mid]] >= endTime[index[i]]) {
                    j = mid;
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            dp[i] = max(dp[i + 1], profit[index[i]] + dp[j]);
        }

        return dp[0];
    }
};

class Solution {
    /**
     * @param {number[]} startTime
     * @param {number[]} endTime
     * @param {number[]} profit
     * @return {number}
     */
    jobScheduling(startTime, endTime, profit) {
        let n = startTime.length;
        let index = Array.from({ length: n }, (_, i) => i);
        index.sort((a, b) => startTime[a] - startTime[b]);

        let dp = new Array(n + 1).fill(0);

        for (let i = n - 1; i >= 0; i--) {
            let left = i + 1,
                right = n,
                j = n;
            while (left < right) {
                let mid = Math.floor((left + right) / 2);
                if (startTime[index[mid]] >= endTime[index[i]]) {
                    j = mid;
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            dp[i] = Math.max(dp[i + 1], profit[index[i]] + dp[j]);
        }

        return dp[0];
    }
}

public class Solution {
    public int JobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.Length;
        int[] index = new int[n];
        for (int i = 0; i < n; i++) index[i] = i;

        Array.Sort(index, (a, b) => startTime[a].CompareTo(startTime[b]));

        int[] dp = new int[n + 1];

        for (int i = n - 1; i >= 0; i--) {
            int left = i + 1, right = n, j = n;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (startTime[index[mid]] >= endTime[index[i]]) {
                    j = mid;
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }

            dp[i] = Math.Max(dp[i + 1], profit[index[i]] + dp[j]);
        }

        return dp[0];
    }
}

func jobScheduling(startTime []int, endTime []int, profit []int) int {
    n := len(startTime)
    index := make([]int, n)
    for i := 0; i < n; i++ {
        index[i] = i
    }
    sort.Slice(index, func(i, j int) bool {
        return startTime[index[i]] < startTime[index[j]]
    })

    dp := make([]int, n+1)

    for i := n - 1; i >= 0; i-- {
        left, right, j := i+1, n, n
        for left < right {
            mid := left + (right-left)/2
            if startTime[index[mid]] >= endTime[index[i]] {
                j = mid
                right = mid
            } else {
                left = mid + 1
            }
        }
        dp[i] = max(dp[i+1], profit[index[i]]+dp[j])
    }

    return dp[0]
}

class Solution {
    fun jobScheduling(startTime: IntArray, endTime: IntArray, profit: IntArray): Int {
        val n = startTime.size
        val index = (0 until n).sortedBy { startTime[it] }.toIntArray()

        val dp = IntArray(n + 1)

        for (i in n - 1 downTo 0) {
            var left = i + 1
            var right = n
            var j = n
            while (left < right) {
                val mid = left + (right - left) / 2
                if (startTime[index[mid]] >= endTime[index[i]]) {
                    j = mid
                    right = mid
                } else {
                    left = mid + 1
                }
            }
            dp[i] = maxOf(dp[i + 1], profit[index[i]] + dp[j])
        }

        return dp[0]
    }
}

class Solution {
    func jobScheduling(_ startTime: [Int], _ endTime: [Int], _ profit: [Int]) -> Int {
        let n = startTime.count
        let index = (0..<n).sorted { startTime[$0] < startTime[$1] }

        var dp = [Int](repeating: 0, count: n + 1)

        for i in stride(from: n - 1, through: 0, by: -1) {
            var left = i + 1, right = n, j = n
            while left < right {
                let mid = left + (right - left) / 2
                if startTime[index[mid]] >= endTime[index[i]] {
                    j = mid
                    right = mid
                } else {
                    left = mid + 1
                }
            }
            dp[i] = max(dp[i + 1], profit[index[i]] + dp[j])
        }

        return dp[0]
    }
}

impl Solution {
    pub fn job_scheduling(start_time: Vec<i32>, end_time: Vec<i32>, profit: Vec<i32>) -> i32 {
        let n = start_time.len();
        let mut index: Vec<usize> = (0..n).collect();
        index.sort_by_key(|&i| start_time[i]);

        let mut dp = vec![0i32; n + 1];

        for i in (0..n).rev() {
            let mut left = i + 1;
            let mut right = n;
            let mut j = n;
            while left < right {
                let mid = left + (right - left) / 2;
                if start_time[index[mid]] >= end_time[index[i]] {
                    j = mid;
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            dp[i] = dp[i + 1].max(profit[index[i]] + dp[j]);
        }

        dp[0]
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

Common Pitfalls

Sorting by End Time Instead of Start Time

For the top-down DP approach, jobs must be sorted by start time so that when we take a job, we can efficiently find the next non-overlapping job. Sorting by end time breaks the forward progression logic and makes binary search for the next valid job incorrect.

Off-by-One Errors in Binary Search

When finding the next non-overlapping job, the condition should be startTime[j] >= endTime[i] (using >= not >). Jobs that start exactly when another ends are non-overlapping. Using strict greater-than excludes valid job combinations and produces suboptimal results.

Forgetting to Handle the Skip Case

At each job, there are two choices: take it or skip it. A common mistake is only considering taking the job and recursing to the next non-overlapping position. You must also consider skipping the current job entirely with dfs(i + 1) and take the maximum of both options.

Using Linear Scan Instead of Binary Search

While a linear scan to find the next non-overlapping job produces correct results, it degrades the time complexity from $O(n \log n)$ to $O(n^2)$ . For large inputs, this causes time limit exceeded errors. Always use binary search to find the next valid job index.

Not Memoizing the Recursion

Without memoization, the recursive solution revisits the same subproblems exponentially many times. Each index can be reached through multiple paths, and recomputing the answer each time leads to exponential time complexity. Always cache the result for each index after computing it.