Java: Maximum Profit in Job Scheduling

class Job{

    int startTime;
    int endTime;
    int profit;

    Job(int start,int end, int profit){
        this.startTime = start;
        this.endTime = end;
        this.profit = profit;
    }
}

class Solution {

    // Will use binary search to find the non overlapping job
    // Returns the latest job that ends before the current job starts.
    public int srch(List<Job> allJobs, int currentJob){

        int start = 0;
        int end = currentJob-1; // As it is 0-based indexing i.e why end=idx-1
        int ans = -1;

        while(start<=end){

            int mid = (start+end)/2;
            // Compare endTime of mid with the startTime of element present idx position
            if(allJobs.get(mid).endTime <= allJobs.get(currentJob).startTime){
                start = mid+1;
                ans  = mid;
            }
            else
                end = mid-1;
        }
        return ans;
    }

    // Using Bottom Up DP
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        
        int noOfJobs = startTime.length;
        List<Job> allJobs = new ArrayList<>();
        for(int i=0;i<noOfJobs;i++){

            allJobs.add(new Job(startTime[i],endTime[i],profit[i]));
        }
        // Sorting by endTime ensures that for any Job i, all possible non-overlapping
        // jobs (ending before ith job) appear before it in sorted order.
        Collections.sort(allJobs, (a,b) -> Integer.compare(a.endTime,b.endTime));

        int[] maxProfit = new int[noOfJobs+1];
        maxProfit[0] = 0; // If there are no jobs, then maxProfit = 0
        
        for(int i=1;i<=noOfJobs;i++){

            int include = allJobs.get(i-1).profit;
            int prevNonOverlappingIndex = srch(allJobs,i-1);

            // As prevNonOverlappingJob idx will come as zero based. Therefore, dp state 
            // corresponding to it will be represented by t[prevNonOverlappingJob+1];
            if(prevNonOverlappingIndex!=-1)
                include += maxProfit[prevNonOverlappingIndex+1];

            int exclude = maxProfit[i-1];
            maxProfit[i] = Math.max(include,exclude);
        }
        return maxProfit[noOfJobs];
    }
}
/*
Golden Note:

1. Sort by endTime when we need to efficiently find the latest non-overlapping event.
2. Sort by startTime when we merge intervals or checking overlaps.
*/