Weighted Job Scheduling

Given N jobs where every job is represented by following three elements of it.

1. Start Time

2. Finish Time

3. Profit or Value Associated (>= 0)

Find the maximum profit subset of jobs such that no two jobs in the subset overlap.

Example:

Input: Number of Jobs n = 4
       Job Details {Start Time, Finish Time, Profit}
       Job 1:  {1, 2, 50} 
       Job 2:  {3, 5, 20}
       Job 3:  {6, 19, 100}
       Job 4:  {2, 100, 200}
Output: The maximum profit is 250.
We can get the maximum profit by scheduling jobs 1 and 4.
Note that there is longer schedules possible Jobs 1, 2 and 3 
but the profit with this schedule is 20+50+100 which is less than 250. 

class Solution {
    static class Job {
        int start, finish, profit;
    }

    public int binarySearch(Job[] jobs, int index) {
        int lo = 0, hi = index - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (jobs[mid].finish <= jobs[index].start) {
                if (jobs[mid + 1].finish <= jobs[index].start)
                    lo = mid + 1;
                else
                    return mid;
            } else
                hi = mid - 1;
        }
        return -1;
    }

    public int schedule(Job[] jobs) {
        Arrays.sort(jobs, (a, b) -> a.finish - b.finish);
        int n = jobs.length;
        int[] table = new int[n];
        table[0] = jobs[0].profit;
        for (int i = 1; i < n; i++) {
            int inclProf = jobs[i].profit;
            int l = binarySearch(jobs, i);
            if (l != -1)
                inclProf += table[l];
            table[i] = Math.max(inclProf, table[i - 1]);
        }
        return table[n - 1];
    }
}