机器调度2.cpp

贪婪算法合集,包括二分覆盖,单源最短路径,拓扑排序,机器调度问题

//练习13-7，调度方法： 假设仅有一台机器可用，那么将选择最大数量的任务在这台机器上执行。
//每步选择一个任务，其贪婪准则是：从剩下的任务中选择具有最小完成时间且不与现有任务重叠的任务。

#include <iostream>
#include "minheap.h"
#include "task2.h"
using namespace std;

void main(void)
{//在一台机器上输出最大任务数的选择
   //输入任务的数目
   int n;  // number of tasks
   cout << "Enter the number of tasks" << endl;
   cin >> n;
   if (n < 1) {cout << "Must be more than 0" << endl;
               exit(1);}

   // 输入并存储这些任务在一个数组t中
   Task *t = new Task [n+1];
   for (int i = 1; i <= n; i++) {
      cout << "Enter the start and finish time of task "
           << i << endl;
      cin >> t[i].start >> t[i].finish;
      if (t[i].start < 0 || t[i].finish <= 0
          || t[i].start >= t[i].finish) {
          cout << "Bad start and/or finish time"
               << endl;
          exit(1);
          }
      t[i].ID = i;//t[i]的id就用i来表示
      }

      // 初始化一个任务完成时间的最小堆
      MinHeap<Task> H(1);
      H.Initialize(t,n,n);

      //开始选择任务
      cout << "The selected tasks are ";
      int avail = 0;  // time machine gets free
      for (i = 1; i <= n; i++) {
         // get task with least finish time
         Task w;
         H.DeleteMin(w);
         if (w.start >= avail) {
             //选择具有最小完成时间且不与现有任务重叠的任务，也即w.start>=start
             cout << w.ID << " ";
             avail = w.finish;
             }
         }  
}