机器调度.cpp

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

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

class Job
{
	friend void TL(Job *, int);
	friend int main();
public:
	operator int () const {return start;}
private:
	char name;
	int start;
	int end;
};

class  MachineNode
{
	friend void TL(Job *, int);
public:
	operator int () const {return avail;}
private:
	int ID,     //机器编号
		avail;  //机器空闲时间
};

template<class T>
void TL(T a[],int n)
{
	HeapSort(a,n);//按升序排列
	MinHeap<MachineNode> H(n);
	int i;
	MachineNode t,x,y;
	//初始化堆的第一个节点
	t.avail=0;
	t.ID=1;
	H.Insert(t);

	//开始插入
	for(i=1;i<=n;i++)
	{
		H.DeleteMin(x);//得到最小空闲时间
		if(a[i].start>=x.avail)//只有比最小时间大的，才能使用这个机器
		{
			cout<<"Job "<<a[i].name<<" on machine "<<x.ID<<" from "<<a[i].start
				<<" to "<<a[i].end<<endl;
			x.avail+=a[i].end-a[i].start;			
			H.Insert(x);
		}
		else
		{//否则先复原最小的x，然后再新开辟一个机器，赋好值之后再插入堆中
			H.Insert(x);
			y.avail=a[i].end;
			y.ID=H.Size()+1;
			cout<<"Job "<<a[i].name<<" on machine "<<y.ID<<" from "<<a[i].start
				<<" to "<<a[i].end<<endl;
			H.Insert(y);
		}
	}
}

int main()
{
	int n;
	cout<<"Input how many jobs: ";
	cin>>n;
	Job *job=new Job[n+1];
	int i;
	for(i=1;i<=n;i++)
	{
		cout<<"Enter Job "<<i <<" such as:a start end\n";
		cin>>job[i].name>>job[i].start>>job[i].end;
	}

	for(i=1;i<=n;i++)
	{
		cout<<job[i].name<<' ';
	}
	cout<<endl;

	TL(job,n);
	return 0;
}