【算法】基于时间段的有限资源算法

1、案例描述
最近做会议管理系统，预约会议需要一个算法来判断在指定的时间段内是否有可用的资源，这个算法是这样的：一个企业可以同时并发的会议数是有限的，预约会议时需要判断在预约的会议时间段内是否有可用的资源，资源没有达到限制数量时可预约会议，一旦资源达到限制的数量则预约会议失败。

举个例子：某企业在同一时间段内可同时并发的最大会议数为4个，企业在2012-12-19已经预订了以下时间段的会议：

编号	开始时间	结束时间
1	2012-12-19 09:00:00	2012-12-19 09:30:00
2	2012-12-19 09:00:00	2012-12-19 10:00:00
3	2012-12-19 09:00:00	2012-12-19 10:30:00
4	2012-12-19 09:30:00	2012-12-19 11:00:00
5	2012-12-19 10:00:00	2012-12-19 10:30:00
6	2012-12-19 10:00:00	2012-12-19 11:00:00
7	2012-12-19 11:00:00	2012-12-19 12:00:00

那么，是否可以预订2012-12-19 10:00:00至2012-12-19 10:40:00的会议？是否可以预订2012-12-19 10:50:00至2012-12-19 11:20:00的会议？

2、案例分析
将已预订的会议和待预订的会议放时间轴上进行分析，如下图所示：


从上图分析可知，在10:00 至10:40之间，该时间段已预订有以下会议：

编号	开始时间	结束时间
3	2012-12-19 09:00:00	2012-12-19 10:30:00
4	2012-12-19 09:30:00	2012-12-19 11:00:00
5	2012-12-19 10:00:00	2012-12-19 10:30:00
6	2012-12-19 10:00:00	2012-12-19 11:00:00

在时间轴标示如下图所示，10:00 至10:40可划分成10:00 至10:30和10:30 至10:40两个时间段来统计资源使用情况。


由上图可知，10:00 至10:30使用了4个，而10:30 至10:40则使用了2个。10:00 至10:30期间并发的会议已达到最大会议数4个的限制，若预订了10:00 至10:40的会议，则在10:00 至10:30期间将超出可并发的最大会议数限制，由此可知，不能再预订10:00至10:40的会议。

同理可知，10:50至11:20之间，可划分为10:50 至11:00和11:00 至11:20两个时间段来统计资源使用情况，其中10:50 至11:00使用了2个，而11:00 至11:20使用了1个，两个时间段都没有达到最大会议数4个的限制，由此可知，可以预订10:50至11:20的会议。

综合上述的分析过程，可以得出处理步骤如下：
（1）获取所有已预约会议中与当前要预约会议时间上有交叉的会议，若获取到的会议数量小于最大会议并发数限制时，则可以预约会议，否则进入（2）；
（2）根据获取的时间上有交叉的已预约会议的开始时间和结束时间，以及当前要预约会议的开始时间和结束时间，划分时间段，并计算在当前要预约会议内每个时间段已使用的资源数；
（3）判断每个时间段已使用的资源数是否已经达到最大会议并发数限制，若有存在某个时间段已使用的资源数已达到，即当前要预约的会议的某个时间段没有资源，不能预约会议，否则可以预约；


3、解决过程
（1）时间段模型TimePeriod

class TimePeriod {
	private String startTime;
	private String endTime;
	
	TimePeriod() {
		
	}
	TimePeriod(String startTime, String endTime) {
		this.startTime = startTime;
		this.endTime = endTime;
	}
	
	public String getStartTime() {
		return startTime;
	}
	
	public void setStartTime(String startTime) {
		this.startTime = startTime;
	}
	
	public String getEndTime() {
		return endTime;
	}
	
	public void setEndTime(String endTime) {
		this.endTime = endTime;
	}
}

（2）获取交叉会议

// 获取列表中与指定时间段有交叉的时间段列表
private static List<TimePeriod> filterPeriods(final TimePeriod source, final List<TimePeriod> resources) {
	List<TimePeriod> results = new ArrayList<TimePeriod>(0);
	String ss = source.getStartTime();
	String se = source.getEndTime();
	for(TimePeriod resource : resources) {
		String rs = resource.getStartTime();
		String re = resource.getEndTime();
		if(!(greaterTime(ss, re) || lessTime(se, rs))) {
			System.out.println("[" + rs + " ~ " + re + "]");
			results.add(resource);
		}
	}
	return results;
}

// 时间比较，time1>=time2时返回true，否则false
private static boolean greaterTime(final String time1, final String time2) {
	return time1.compareTo(time2)>=0;
}

// 时间比较，time1<=time2时返回true，否则false
private static boolean lessTime(final String time1, final String time2) {
	return time1.compareTo(time2)<=0;
}

（3）获取时间点

// 获取列表中与给定时间段内的所有时间点
private static Map<String, String> listPoints(final TimePeriod source, final List<TimePeriod> resources) {
	Map<String, String> points = new HashMap<String, String> (0);
	addPoint(source, points);
	
	for(TimePeriod resource : resources) {
		addPoint(source, resource, points);
	}
	return points;
}
// 加入时间点
private static void addPoint(final TimePeriod source, Map<String, String> points) {
	addPoint(source, source, points);
}

// 加入时间点
private static void addPoint(final TimePeriod source, final TimePeriod period, Map<String, String> points) {
	addPoint(source, period.getStartTime(), points);
	addPoint(source, period.getEndTime(), points);
}

// 加入时间点
private static void addPoint(final TimePeriod source, final String time, Map<String, String> points) {
	if(greaterTime(time, source.getStartTime()) && lessTime(time, source.getEndTime())) {
		if(!points.containsKey(time)) {
			points.put(time, time);
		}
	}
}

（4）对时间点进行排序

private static String[] sortPoints(final Map<String, String> points) {
	int index = 0;
	String[] results = new String[points.size()];
	for(String key : points.keySet()) {
		results[index ++] = key;
	}
	Arrays.sort(results);
	return results;
}

（5）划分时间段

// 根据排序好的时间点，划分相关时间段
private static List<TimePeriod> listPeriods(final String[] points) {
	List<TimePeriod> spans = new ArrayList<TimePeriod> (0);
	String start = points[0];
	for(int i=1; i<points.length; i++) {
		spans.add(new TimePeriod(start, points[i]));
		start = points[i];
	}
	return spans;
}

（6）计算每个时间段已使用资源数

// 计算每个时间段已使用的资源数
private static int[] cacl(final List<TimePeriod> periods, final List<TimePeriod> resources) {
	int[] results = new int[periods.size()];
	for(TimePeriod resource : resources) {
		for(int i=0; i<periods.size(); i++) {
			if(checkSpan(periods.get(i), resource)) {
				results[i] ++;
			}
		}
	}
	printResult(periods, results);
	return results;
}

// 检查是否已指定时间段有交叉
private static boolean checkSpan(final TimePeriod period, final TimePeriod resource) {
	String ss = period.getStartTime();
	String se = period.getEndTime();
	String rs = resource.getStartTime();
	String re = resource.getEndTime();
	return(greaterTime(ss,rs) && lessTime(se,re));
}

// 打印输出各时间段资源使用情况
private static void printResult(final List<TimePeriod> periods, final int[] results) {
	for(int i=0; i<results.length; i++) {
		TimePeriod r = periods.get(i);
		System.out.println("[" + r.getStartTime() + " ~ " + r.getEndTime() + "]=" + results[i]);
	}
}

（7）判断是否有可用资源

// 判断是否有可用资源，有则返回true，否则返回false
private static boolean canBooked(final int max, final TimePeriod source, final List<TimePeriod> resources) {
	return canBooked(max, cacl(listPeriods(sortPoints(listPoints(source, resources))), resources));
}
// 判断已使用的资源数是否存在已超过或等于最大值，是则返回false，否则返回true
private static boolean canBooked(final int max, final int[] results) {
	for(int result : results) {
		if(result>=max) {
			return false;
		}
	}
	return true;
}

4、解决结果
（1）测试代码

public static void main(String[] args) {
	int maxResource = 4;
	TimePeriod source1 = new TimePeriod("2012-12-19 10:00:00","2012-12-19 10:40:00");
	TimePeriod source2 = new TimePeriod("2012-12-19 10:50:00","2012-12-19 11:20:00");
	List<TimePeriod> resources = new ArrayList<TimePeriod> (0);
	resources.add(new TimePeriod("2012-12-19 09:00:00","2012-12-19 09:30:00"));
	resources.add(new TimePeriod("2012-12-19 09:00:00","2012-12-19 10:00:00"));
	resources.add(new TimePeriod("2012-12-19 09:00:00","2012-12-19 10:30:00"));
	resources.add(new TimePeriod("2012-12-19 09:30:00","2012-12-19 11:00:00"));
	resources.add(new TimePeriod("2012-12-19 10:00:00","2012-12-19 10:30:00"));
	resources.add(new TimePeriod("2012-12-19 10:00:00","2012-12-19 11:00:00"));
	resources.add(new TimePeriod("2012-12-19 11:00:00","2012-12-19 12:00:00"));
	
	if(canBooked(maxResource, source1, resources)) {
		System.out.println("Yes");
	} else {
		System.out.println("No");
	}
	
	System.out.println();
	if(canBooked(maxResource, source2, resources)) {
		System.out.println("Yes");
	} else {
		System.out.println("No");
	}
}

（2）运行结果

[2012-12-19 09:00:00 ~ 2012-12-19 10:30:00]
[2012-12-19 09:30:00 ~ 2012-12-19 11:00:00]
[2012-12-19 10:00:00 ~ 2012-12-19 10:30:00]
[2012-12-19 10:00:00 ~ 2012-12-19 11:00:00]
[2012-12-19 10:00:00 ~ 2012-12-19 10:30:00]=4
[2012-12-19 10:30:00 ~ 2012-12-19 10:40:00]=2
No

[2012-12-19 09:30:00 ~ 2012-12-19 11:00:00]
[2012-12-19 10:00:00 ~ 2012-12-19 11:00:00]
[2012-12-19 11:00:00 ~ 2012-12-19 12:00:00]
[2012-12-19 10:50:00 ~ 2012-12-19 11:00:00]=2
[2012-12-19 11:00:00 ~ 2012-12-19 11:20:00]=1
Yes

（3）结论
从运行结果可知，测试结果正确，问题解决。

5、完整源代码
完整源代码  点击这里  下载