import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
public class GraphColoringProblem {
/**编程之美 高效地安排会议 图着色问题 贪心算法
* 假设要用很多个教室对一组活动进行调度。我们希望使用尽可能少的教室来调度所有的活动。请给出一个有效的贪心算法,来确定哪一个活动应使用哪一个教室。
* (这个问题也被成为区间图着色(interval-graph coloring)问题。我们可作出一个区间图,其顶点为已知的活动,其边连接着不兼容的活动。
* 为使任两个相邻结点的颜色均不相同,所需的最少颜色对应于找出调度给定的所有活动所需的最少教室数。)
* see
* http://renren.it/a/caozuoxitong/OS/20120626/176363.html
*/
public static void main(String[] args) {
List<Meeting> list=new ArrayList<Meeting>();
Random random=new Random();
for(int i=0;i<10;i++){
int begin=random.nextInt(10)+1;
int end=begin+(random.nextInt(10)+1);
Meeting meeting=new Meeting(begin,end);
list.add(meeting);
}
GraphColoringProblem gcp=new GraphColoringProblem();
gcp.smartManagment(list);
}
public void smartManagment(List<Meeting> list){
if(list==null||list.size()<2){
return;
}
printList(list);
Collections.sort(list);
printList(list);
List<List<Meeting>> outerList=new ArrayList<List<Meeting>>();
while(list.size()!=0){
int size=list.size();
List<Meeting> listOfOneRoom=new ArrayList<Meeting>();
Meeting current=list.get(0);
listOfOneRoom.add(current);
for(int i=1;i<size;i++){
Meeting candidate=list.get(i);
if(candidate.begin>=current.end){
listOfOneRoom.add(candidate);
current=candidate;
}
}
outerList.add(listOfOneRoom);
list.removeAll(listOfOneRoom);
}
//meetings that can be held in the same room are printed in one line:
for(int i=0,size=outerList.size();i<size;i++){
printList(outerList.get(i));
}
}
static class Meeting implements Comparable<Meeting>{
int begin;
int end;
Meeting(int begin,int end){
this.begin=begin;
this.end=end;
}
public int compareTo(Meeting o) {
int endCmp=this.end-o.end;
if(endCmp==0){
return this.begin-o.begin;
}
return endCmp;
}
public String toString(){
return "["+begin+","+end+"]";
}
}
public static void printList(List<Meeting> list){
if(list==null||list.size()==0){
return;
}
for(int i=0,size=list.size();i<size;i++){
System.out.print(list.get(i));
}
System.out.println();
}
}
分享到:
相关推荐
(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务: 对于给定的k个待安排的活动,编程计算...
C语言是一门通用计算机编程语言,广泛应用于底层开发。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码
设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务: 对于...
设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务: 对于...
设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务: 对于...
涉及矩阵链相乘问题、投资问题、背包问题、旅行商问题(TSP)、数字三角形、哈夫曼编码、顾客等待时间最短问题、最小生成树问题、图着色问题、八皇后问题、连续邮资问题、卫兵布置问题、圆排列问题、最近对问题、...
张伟达 -《用改进算法的思想解决规模维数增大的问题》 黄 刚 -《数据结构的联合》 杨 弋 -《从“小H的小屋”的解法谈算法的优化》 朱晨光 -《浅析倍增思想在信息学竞赛中的应用》 李羽修 -《Hash函数的设计优化...
2012-06-12 11:51 240,128 最小生成树(prim算法)贪心算法.doc 2012-06-12 12:26 772,419 最简单的c++静态链接.zip 2012-06-12 11:45 202,240 最长公共子序列算法.doc 2012-06-12 12:24 956 步进电机C程序.c 2012-...
设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。)编程任务:对于给定...