作业调度问题|集合3（利用Java中的TreeSet实现）

Input : Four Jobs with following deadlines and profits
JobID Deadline Profit
a 4 20
b 1 10
c 1 40
d 1 30
Output : Following is maximum profit sequence of jobs
c, a


Input : Five Jobs with following deadlines and profits
JobID Deadline Profit
a 2 100
b 1 19
c 2 27
d 1 25
e 3 15
Output : Following is maximum profit sequence of jobs
c, a, e


import java.io.*;
import java.util.*;
public class Solution {
    // Job class
    public static class Job {
        char id;
        int deadline;
        int profit;
        // Constructor
        Job(char id, int deadline, int profit)
        {
            this.id = id;
            this.deadline = deadline;
            this.profit = profit;
        }
    }
    public static class Sorted implements Comparator {
        // Function to implement comparator
        public int compare(Object o1, Object o2)
        {
            Job j1 = (Job)o1;
            Job j2 = (Job)o2;
            if (j1.profit != j2.profit)
                return j2.profit - j1.profit;
            else
                return j2.deadline - j1.deadline;
        }
    }
    // Function to print job scheduling
    public static void printJobScheduling(Job jobs[], int n)
    {
        // Creating object of Sorted class
        Sorted sorter = new Sorted();
        Arrays.sort(jobs, sorter);
        // Creating TreeSet Object
        TreeSet<Integer> ts = new TreeSet<>();
        for (int i = 0; i < n; i++)
            ts.add(i);
        for (int i = 0; i < n; i++) {
            Integer x = ts.floor(jobs[i].deadline - 1);
            if (x != null) {
                System.out.print(jobs[i].id + " ");
                ts.remove(x);
            }
        }
    }
    // Driver Code
    public static void main(String[] args)
    {
        int n = 5;
        Job[] jobs = new Job[n];
        jobs[0] = new Job('a', 2, 100);
        jobs[1] = new Job('b', 1, 19);
        jobs[2] = new Job('c', 2, 27);
        jobs[3] = new Job('d', 1, 25);
        jobs[4] = new Job('e', 3, 15);
        printJobScheduling(jobs, n);
    }
    // Contributed by Dipesh Jain (dipesh_jain)
}