schedule.cpp

常用算法与数据结构原代码

#include <iostream.h>

template<class T>
inline void Swap(T& a, T& b)
{
	T temp = a; a = b; b = temp;
}

template<class T>
int Max(T a[], int n)
{
	int pos = 0;
	for (int i = 1; i < n; i++)
		if (a[pos] < a[i])
			pos = i;
	return pos;
}

int *E;

void Initialize(int n)
{
	// Initialize n classes with one element each.
	E = new int [n + 1];
	for (int e = 0; e <= n; e++)
		E[e] = e;
}

void Union(int i, int j, int n)
{
	// Union the classes i and j.
	if (i >= j)
	{
		for (int k = 0; k <= n; k++)
		{
			if (E[k] == j) 
				E[k] = i;
		}
	}
	else
	{
		for (int k = 0; k <= n; k++)
		{
			if (E[k] == i) 
				E[k] = j;
		}
	}
}

int Find(int e)
{
	// Find the class that contains element e.
	return E[e];
}

void main(void)
{
	int i, j, k;
	bool bSucc;

	int n = 4;		// 时间段的数目，和任务数相同
	int *DeadLine;
	DeadLine = new int [n + 1];	// 最后期限
	DeadLine[1] = 2;
	DeadLine[2] = 4;
	DeadLine[3] = 2;
	DeadLine[4] = 3;

	int *Start, *StartForSort;
	Start = new int [n + 1];	// 释放时间
	StartForSort = new int [n + 1];
	StartForSort[0] = -1;
	StartForSort[1] = Start[1] = 0;
	StartForSort[2] = Start[2] = 0;
	StartForSort[3] = Start[3] = 1;
	StartForSort[4] = Start[4] = 2;

	int *Sequence;
	Sequence = new int [n];	// 分配次序
	for (i=0; i<n; i++)
		Sequence[i] = i+1;

	for (i=n+1, k=0; i>1; i--) 
	{
		int j = Max(StartForSort, i);
		Swap(StartForSort[j], StartForSort[i - 1]);
		Swap(Sequence[j-1], Sequence[i-2]);
	}
	delete []StartForSort;

	Initialize(n);
	int *Assign;
	Assign = new int [n];	
	
	for (i=n-1; i>=0; i--)
	{
		bSucc = false;
		int JobNum = Sequence[i];
		for (j=DeadLine[JobNum]; j>Start[JobNum]; j--)
		{
			int sect = Find(j);
			if (sect == 0)
				continue;

			Assign[JobNum-1] = sect;
			Union(Find(sect-1), sect, n);
			bSucc = true;
			break;
		}
		
		if (!bSucc)
			break;
	}
			
	if (bSucc)
	{
		cout << "Assign time as followed:" << endl;
		for (i=0; i<n; i++)
			cout << "Job " << i+1 << ": " << Assign[i]-1 << "~" << Assign[i] << endl;
	}
	else
	{
		cout << "Assign time failed!" << endl;
	}

	delete []E;
	delete []DeadLine;
	delete []Start;
	delete []Sequence;
	delete []Assign;
}