有期限的作业排序问题

在此问题中，给出了一份作业列表。在列表中，还列出了每个工作的截止日期和利润。每个工作将占用一个单位时间，因此，一个工作的最短期限是1。如果一次只能安排一个工作，则可以最大程度地提高利润。

为了解决该问题，生成作业组的所有子集以检查单个子集是否可行。此外，跟踪已生成的所有可行子集的最大利润。

该算法的时间复杂度为O（n ^ 2）

输入输出

Input:
A list of jobs with job id, deadline and profit. And the number of jobs n.
{('a', 2, 100), ('b', 1, 19), ('c', 2, 27), ('d', 1, 25), ('e', 3, 15)}
n = 5
Output:
Following is maximum profit sequence of job sequence: c a e

算法

jobSequence(jobList, n)

输入-作业列表以及列表中存在的作业数。

输出-顺序，如何进行作业。

Begin
   sort the jobs in jobList according to their profit create a list of job sequence and slot to track free time slots
   initially make all slots are free
   for all given jobs i do
      for all jobs in the list from ending of the list do
         if slot[j] is free then
            jobSequence[j] := i
            make slot[j] := fill
            break the loop
      done
   done

   for all slots when it is not free do
      print id of job using jobList[jobSequence[i]]
   done
End

示例

#include<iostream>
#include<algorithm>
using namespace std;

struct Job {
   char id;
   int deadLine;
   int profit;
};

bool comp(Job j1, Job j2) {
   return (j1.profit > j2.profit);    //compare jobs based on profit
}

int min(int a, int b) {
   return (a<b)?a:b;
}

void jobSequence(Job jobList[], int n) {
   sort(jobList, jobList+n, comp);    //sort jobList on profit

   int jobSeq[n];     // To store result (Sequence of jobs)
   bool slot[n];      // To keep track of free time slots

   for (int i=0; i<n; i++)
      slot[i] = false; //initially all slots are free

   for (int i=0; i<n; i++) {    //for all given jobs
      for (int j=min(n, jobList[i].deadLine)-1; j>=0; j--) {   //search from last free slot
         if (slot[j]==false) {
            jobSeq[j] = i;   // Add this job to job sequence
            slot[j] = true;  // mark this slot as occupied
            break;
         }
      }
   }

   for (int i=0; i<n; i++)
      if (slot[i])
         cout << jobList[jobSeq[i]].id << " ";    //display the sequence
}

int main() {
   Job jobList[] = {{'a',2,100}, {'b',1,19}, {'c',2,27},{'d',1,25},{'e',3,15}};
   int n = 5;
   cout << "Following is maximum profit sequence of job sequence: ";
   jobSequence(jobList, n);
}

输出结果

Following is maximum profit sequence of job sequence: c a e