WeightedJobSchedulingBinarySearch.java

import java.util.Arrays;

public class WeightedJobSchedulingBinarySearch {

    static class Job {
        int start_time;
        int end_time;
        int weight;

        public Job(int start_time, int end_time, int weight) {
            this.start_time = start_time;
            this.end_time = end_time;
            this.weight = weight;
        }
    }
    public static int findMaxWeight(Job[] jobs) {
        Arrays.sort(jobs, (o1, o2) -> o1.end_time - o2.end_time);
        int n = jobs.length;
        int[] dp = new int[n];
        dp[0] = jobs[0].weight;

        for (int i = 1; i < n; i++) {
            int maxWeight = jobs[i].weight;
            int latestNonOverlappingJob = findLatestNonOverlappingJob(jobs, i);

            if (latestNonOverlappingJob != -1) {
                maxWeight += dp[latestNonOverlappingJob];
            }

            dp[i] = Math.max(maxWeight, dp[i-1]);
        }

        return dp[n-1];
    }

    public static int findLatestNonOverlappingJob(Job[] jobs, int currentIndex) {
        int low = 0;
        int high = currentIndex - 1;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (jobs[mid].end_time <= jobs[currentIndex].start_time) {
                if (jobs[mid + 1].end_time <= jobs[currentIndex].start_time) {
                    low = mid + 1;
                } else {
                    return mid;
                }
            } else {
                high = mid - 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        Job[] jobs = {
                new Job(1, 4, 3),
                new Job(2, 6, 5),
                new Job(4, 7, 2),
                new Job(6, 8, 6),
                new Job(5, 9, 4),
                new Job(7, 10, 8)
        };

        int maxWeight = findMaxWeight(jobs);
        System.out.println("Maximum Weight: " + maxWeight);
    }
}