题目：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点有不同颜色的最小着色数，相应于要找的最小会场数。
我写的程序：
//本程序默认文件中的活动已经按结束时间的非减续进行了排列
import java.io.*;
class A //用类A来描述活动的相关属性
{
public int start; //活动的起始时间
public int end; //活动的结束时间
public int place; //活动被分到的会场
public boolean arrange = false; //通过arrange判断待安排的某个活动是否已经得到了安排，初始值默认为false
}
class B
{
public int num; //用来存放待安排的活动数量
public A[] acts;
public void f() //本函数的目的是从本文当中获取信息并将数据存放到数组acts当中
{
try
{
//先通过流的知识将本件中的数据进行读取
FileReader fr = new FileReader("C:\\Users\\Administrator\\Desktop\\input.txt");
BufferedReader fr2 = new BufferedReader(fr); //本程序将要利用缓冲流中的方法readLine()读取文本行
String str = fr2.readLine();//先将待安排的活动的数量k读取出来
num = Integer.valueOf(str);
System.out.println("待安排的活动共有:" + num + "个");
str = fr2.readLine();//从文本文件中读取第二行文本： 1 23
acts = new A[num]; //new出num个需要安排的对象
int i = 0;//给第一个需要安排的活动编号为0,即初始化
while(num!=0) //若待安排的活动数量不为0
{
acts[i] = new A();//动态分配一块内存空间,空间中包括了属性与方法
//对字符串str进行切分,获取初始时间和结束时间
String[] time = str.trim().split(" ");
acts[i].start = Integer.valueOf(time[0]);
acts[i].end = Integer.valueOf(time[1]);
System.out.printf("%d %d\n",acts[i].start,acts[i].end);
str = fr2.readLine();//从文本文件中继续读取数据
i ++;
}
}catch(Exception e2){} //捕获数组下标越界异常,使程序的流程继续执行
}
public void greedySelect() //编写贪心选择代码
{
f();
int convention = 1;
for(int i=0;(i<num)&&(!acts[i].arrange);i++)
{
acts[i].arrange = true;
acts[i].place = convention;//贪心选择算法默认将结束时间最小的放在了0会场
for(int j=1;(j<num)&&(!acts[j].arrange);j++) //依次比较下一个start时间是否大于上一个end时间
{
int k = i;
if(acts[j].start>=acts[k].end) //看是否相容
{
acts[j].place = convention;//可以放到同一个会场
acts[j].arrange = true;
k = j; //接着比较下一个活动时间
}
}
convention ++;
}
System.out.println("使用的会场数量为：" + convention);
//最后将最少使用的会场数量输出到指定的文件output.txt当中
try
{
PrintStream fw = new PrintStream("C:\\Users\\Administrator\\Desktop\\output.txt");//修改输出路径
System.setOut(fw);
System.out.printf("%d",convention);
}catch(Exception e3){}
}
}
public class zhang22
{
public static void main(String[] args)
{
try
{
new B().greedySelect();
} catch(Exception ee){}
}
}
运行结果：
待安排的活动共有:6个
1 23
12 28
25 35
27 80
36 50
1 100
使用的会场数量为：3
正常的结果应该是会场的数量为：4
我感觉是贪心算法的那两个for循环出错了，但是改了一下午，一直改不对，大家帮我看一下，谢谢