Maximum Profit in Job Scheduling

1public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
2    int n = startTime.length;
3    int[][] jobs = new int[n][3];
4    for (int i = 0; i < n; i++) {
5        jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
6    }
7    Arrays.sort(jobs, (a, b) -> a[1] - b[1]);
8
9    int[] dp = new int[n];
10    dp[0] = jobs[0][2];
11
12    for (int i = 1; i < n; i++) {
13        int includeProfit = jobs[i][2];
14        int l = binarySearch(jobs, i);
15        if (l != -1) {
16            includeProfit += dp[l];
17        }
18        dp[i] = Math.max(includeProfit, dp[i - 1]);
19    }
20
21    return dp[n - 1];
22}
23
24private int binarySearch(int[][] jobs, int index) {
25    int low = 0, high = index - 1;
26    while (low <= high) {
27        int mid = low + (high - low) / 2;
28        if (jobs[mid][1] <= jobs[index][0]) {
29            if (mid + 1 < index && jobs[mid + 1][1] <= jobs[index][0]) {
30                low = mid + 1;
31            } else {
32                return mid;
33            }
34        } else {
35            high = mid - 1;
36        }
37    }
38    return -1;
39}