贪心算法解决会场活动安排
问题描述:
在足够多的教室里安排一批课程,并希望使用尽可能少的教室。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个课程作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小教室数。) 编程任务:
对于给定的k个待安排的课程,编程计算使用最少教室的时间表。 数据输入:
由文件或键盘给出输入数据。第一行有1 个正整数k,表示有k个待安排的课程。接下来的k行中,每行有2个正整数,分别表示k个待安排的课程开始时间和结束时间。时间以0 点开始的分钟计。 结果输出:
将编程计算出的最少教室数及各教室中的课程编号输出到文件或屏幕。
using System;
namespace 教室安排问题 {
class Class1 {
static void Main(string[] args) {
int num=0; int temp=0;
int[] ans=new int[] {-1};
Console.Write("Please input how many numbers to input:\n"); num =
int.Parse(Console.ReadLine().ToString());
int[] s=new int[num]; int[] f=new int[num];
int[] A=new int[num];//表示是否已经安排了教室的课程。0为没有安排hc,1为当前正在安排教室,2为已经安排了教室!
Console.WriteLine("Input starttime and endtime");
for(temp=0;temp
string ls = Console.ReadLine(); char[] cc={' '};
string[] ss =ls.Split(cc);
s[temp]=int.Parse(ss[0].ToString()); f[temp]=int.Parse(ss[1].ToString()); }
temp = 0; int number = 0; bool end =false;
while(!end)//当没有把所有的教室都安排完的时候就继续安排教室! {
number++;
GreedySelector(num,s,f,A);
Console.WriteLine("最终结果课程输出是:"); end = true;// 假设当前教室能够把剩余的课程都安排进去!
for(temp=0;temp
if(A[temp]==1) {
Console.WriteLine("课程{0}",temp+1); }
if(A[temp]==0)
end = false;//只要有一个课程没有安排进去就要继续进行while循环! } }
Console.ReadLine(); }
static void GreedySelector(int num,int[] s,int[] f,int[] A)
{//进行排教室的主要算法! int i,temp; int j=0;
for(temp=0;temp
if(A[temp]==0) {
j=temp+1; A[temp]=1; break; } else A[temp]=2; j=i; } else A[i]=2; } else
if(A[i]!=2) A[i]=0; } }
private static void changeNum(ref int num1,ref int num2) {
int temp=num1; num1=num2; num2=temp;
}
private static void sort(int num,int[] s,int[] f)
{ /*将用户输入的教室时间安排顺序输出!*/
int temp1 = 0,temp2=0; for(;temp1
int min=f[temp1];
int v=temp1; /*保存最小的数的下标!*/
for(temp2=temp1;temp2
{//选择排序法 if(f[temp2]
min=f[temp2]; v=temp2; } }
changeNum(ref s[temp1],ref s[v]); changeNum(ref f[temp1],ref f[v]); } } }}