作业排序问题|集合3（在JAVA中使用TreeSet）-yiteyi-C++库

给定一系列工作，其中每个工作都有一个截止日期和相关利润（如果工作在截止日期之前完成）。此外，每项工作都需要一个单位的时间，因此任何工作的最小可能截止日期为1。如果一次只能安排一项工作，如何最大化总利润。

null

例如：

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

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

下面是在Java中使用TreeSet解决问题的分步算法：

根据各自的利润按降序对所有工作进行排序。
创建一个树集并插入0到n-1之间的所有整数。
遍历一系列作业，为我 ^th 工作
- 在树集中搜索最大值小于i截止日期的时间段“x” ^th 工作
- 如果存在任何值，则在答案中包含该作业，并从树集中删除“x”
- 否则，检查剩余的工作。

以下是上述算法的实现：

                     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)                   
                     }                   

时间复杂性 ：O（N*log（N）） 辅助空间 ：O（N）

文章版权归作者所有，未经允许请勿转载。

THE END

Java