当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

编程之美-高效地安排会议 图着色问题 贪心算法

发表于: 2012-07-23   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Random; public class GraphColoringProblem { /**编程之美 高效地安排会议 图着色问题 贪心算法 * 假设要用很多个教室对一组

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();
	}
}

编程之美-高效地安排会议 图着色问题 贪心算法

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
图的m色判定问题: 给定无向连通图G和m种颜色。用这些颜色为图G的各顶点着色.问是否存在着色方法,使
《编程之美》读书笔记 ( 四 ) :卖书折扣问题的贪心解法 每次看完《编程之美》中的问题,想要亲自演
《编程之美》读书笔记 ( 四 ) :卖书折扣问题的贪心解法 每次看完《编程之美》中的问题,想要亲自演
《编程之美》读书笔记 ( 四 ) :卖书折扣问题的贪心解法 每次看完《编程之美》中的问题,想要亲自演
《编程之美》读书笔记 ( 四 ) :卖书折扣问题的贪心解法 每次看完《编程之美》中的问题,想要亲自演
《编程之美》读书笔记 ( 四 ) :卖书折扣问题的贪心解法 每次看完《编程之美》中的问题,想要亲自演
问题表述:设有n个活动的集合E = {1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在
//活动安排问题 public class Activearr { public static int greedselector(int [] s,int [] f,boo
类似的问题是:选点问题和区间覆盖问题。 活动安排问题就是要在所给的活动集合中选出最大的相容活动
活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合,是可以用贪心算法有效求解的很好
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号