WeightedJobScheduling.java

import java.util.Arrays;

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 class WeightedJobScheduling {
    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) {
        for (int i = currentIndex - 1; i >= 0; i--) {
            if (jobs[i].end_time <= jobs[currentIndex].start_time) {
                return i;
            }
        }
        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);
    }
}