- 浏览: 532027 次
- 性别:
- 来自: 上海
-
文章分类
最新评论
-
zfx1982:
楼主能把doubango和webrtc2sip的源码发我一份么 ...
CentOS下编译webrtc2sip实战 -
zfx1982:
请问在编译doubango的时候configure总是说少sr ...
CentOS下编译webrtc2sip实战 -
cgs1999:
845896876 写道老师你好,我发现// 自定义属性 ...
使用Java操作LDAP案例 -
845896876:
老师你好,我发现// 自定义属性 a ...
使用Java操作LDAP案例 -
myitela:
NAT即地址转换,也可以是内网地址与外网地址的转换。如nat1 ...
NAT与NAT穿越学习总结
1、案例描述
最近做会议管理系统,预约会议需要一个算法来判断在指定的时间段内是否有可用的资源,这个算法是这样的:一个企业可以同时并发的会议数是有限的,预约会议时需要判断在预约的会议时间段内是否有可用的资源,资源没有达到限制数量时可预约会议,一旦资源达到限制的数量则预约会议失败。
举个例子:某企业在同一时间段内可同时并发的最大会议数为4个,企业在2012-12-19已经预订了以下时间段的会议:
那么,是否可以预订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之间,该时间段已预订有以下会议:
在时间轴标示如下图所示,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
(2)获取交叉会议
(3)获取时间点
(4)对时间点进行排序
(5)划分时间段
(6)计算每个时间段已使用资源数
(7)判断是否有可用资源
4、解决结果
(1)测试代码
(2)运行结果
(3)结论
从运行结果可知,测试结果正确,问题解决。
5、完整源代码
完整源代码 点击这里 下载
最近做会议管理系统,预约会议需要一个算法来判断在指定的时间段内是否有可用的资源,这个算法是这样的:一个企业可以同时并发的会议数是有限的,预约会议时需要判断在预约的会议时间段内是否有可用的资源,资源没有达到限制数量时可预约会议,一旦资源达到限制的数量则预约会议失败。
举个例子:某企业在同一时间段内可同时并发的最大会议数为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、案例分析
将已预订的会议和待预订的会议放时间轴上进行分析,如下图所示:
![](http://dl.iteye.com/upload/attachment/0081/2717/bee0a6fb-7944-3fe7-92fd-14f89e0a9bb2.png)
从上图分析可知,在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两个时间段来统计资源使用情况。
![](http://dl.iteye.com/upload/attachment/0081/2719/6ee1b37e-3bc3-3189-bd54-f47b2cce7a8b.png)
由上图可知,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、完整源代码
完整源代码 点击这里 下载
发表评论
-
MySQL中Update的执行效率测试及验证
2016-12-06 16:22 68271、引言 某日,在讨论解决生产环境的问题时,一同事问说增加条件 ... -
MySQL定时器实战
2016-11-29 17:38 21321、引言 项目商用环境上,用户反馈有个统计存在问题,排查后 ... -
用Java实现N*N的标准数独及对角线数独解题
2016-10-11 11:25 35151、引言 前一段时间迷 ... -
在Spring项目中实现动态创建数据库
2017-06-21 16:31 52101、问题描述 在使用Sprin ... -
改进现有架构支持HTTPS服务
2016-06-23 16:57 01、引言 nginx使用ssl模块配置HTTPS支持 ht ... -
CentOS下从源码安装Asterisk实战
2016-05-20 20:23 36190、引言 在研究WebRTC服 ... -
EasyUI学习(1)- 入门
2015-12-14 17:20 00、引言 前段时间,在项目开发过程中使用了EasyUI的部分组 ... -
JS实现的3级联动例子
2015-06-17 23:10 1366朋友项目需要实现3级联动,需要JS实现的,网上找的例子有些复杂 ... -
JSBuilder2介绍及应用范例
2014-08-27 17:58 01、引言 Web项目开发过程中,使用到多个第三方的插件,同时, ... -
实现CSS样式文件中图标的可视化
2014-06-26 14:39 4982关键词: CSS,EasyUI ... -
jquery选择器学习范例
2014-04-22 20:54 0http://www.w3school.com.cn/jque ... -
通过webrtc2sip实现web客户端sipML5与SIP客户端Jtisi对通
2014-01-13 19:53 00、引言 在研究WebRTC服 ... -
NAT与NAT穿越学习总结
2013-12-23 19:19 204671、引言网络地址转换 ... -
完全清除Desktop_1.ini和Desktop_2.ini
2013-12-06 17:21 71651、引言 Windows7工作机进入系统就会弹出“deskto ... -
CentOS下搭建Asterisk+SIPml5实战
2013-11-14 14:53 00、引言 在研究SIPml5信令处理时,需要搭建环境SIPml ... -
CentOS下编译webrtc2sip实战
2013-11-13 10:39 152250、引言 在研究WebRTC服 ... -
Java实现RTP流转发服务器
2013-10-24 17:36 00、引言 在做多方视频会议系统时,需要有代理服务器来转发视频平 ... -
利用mysql日志排查数据异常问题
2013-03-21 16:52 01、案例描述 2、MySQL日志 3、解决过程 (1) ... -
Java中通过MySQL的行锁解决并发写的问题
2012-12-22 12:45 01、案例描述 开发会议管理项目中,涉及会议管理系统和视频会议平 ... -
API测试范例
2012-10-29 18:38 01、MessagesAPITest package com ...
相关推荐
本实验聚焦于“基于优先级的时间片轮转调度算法”,这是一种兼顾响应时间和系统效率的调度策略。以下是对该算法及其相关知识的详细阐述。 时间片轮转调度算法是一种多任务调度方式,它的基本思想是将所有就绪进程放...
模拟操作系统 进程模拟调度算法 基于时间片
本文以大规模成品油二次配送路径规划为对象,研究了具有成品油物流特征的多车场带时间窗的车辆路径问题的数学模型,提出了新的基于子问题分解的两阶段优化算法....
Dijkstra算法基于贪心策略,每次扩展当前最短路径节点,直到到达目标节点。虽然Dijkstra算法在处理大规模网络时效率较低,但它能够保证找到精确的最短路径,对于简单的二维路径规划问题非常适用。 结合蚁群算法和...
该描述表明,这个项目不仅关注于解决车间调度问题,同时也作为一个学习资源,帮助用户理解遗传算法的原理和实现方式,特别是如何利用MATLAB编程语言来构建和执行这种算法。MATLAB作为一种强大的数值计算和数据可视化...
本话题将深入探讨如何利用C语言实现基于字符串模式匹配算法的病毒感染检测。 首先,我们需要了解字符串模式匹配的基本概念。在这一背景下,我们有一个目标字符串(通常代表一段文件内容)和一个模式字符串(可能是...
网格计算是解决科学计算、工程计算和商业计算等大规模计算的下一代极具潜力的计算平台。... 3)根据基本遗传算法和蚁群算法的本质特征以及网格计算环境对任务调度的要求,设计了基于遗传算法和议群算法的网格任务调度策略
在基于CCS的卷积算法仿真实验中,我们首先需要理解卷积运算的数学基础,包括线性代数和离散时间信号处理的基本概念。接着,我们需要熟悉CCS的工作流程,创建项目、编写源代码、配置编译器选项以及设置调试参数。源...
针对以完工时间最小化为目标的置换流水车间调度问题(PFSP),提出了一种基于分布估计算法的二阶段置换流水车间调度算法。首先,在算法的第一阶段采用分布估计算法对PFSP进行优化得到一个局部最优解;为了进一步提高...
这个时间段即为单个cell的传输时间。通过多次测量,我们可以得到多个cell传输时间的样本,从而计算平均值作为平均传输时间。 4. **调整参数**:在实际应用中,可能会遇到网络拥塞、丢包等问题,这会导致传输时间的...
基于并行人工免疫算法的大规模TSP问题求解-基于并行人工免疫算法的大规模TSP问题求解.pdf 摘 要: 为求解大规模TSP 问题,提出了并行人工免疫系统的塔式主从模型 ,和基于TMSM的并行免疫记忆克隆选择算法 . TMSM是...
4. **实时性能**:AE算法需要在短时间内完成计算并调整曝光,这对计算资源和算法效率提出了挑战。 5. **人工智能集成**:现代的AE算法往往结合机器学习和深度学习技术,通过训练模型预测最佳曝光设置,提高自动化...
这些算法通常在固定分区分配的内存管理策略中使用,适用于内存资源有限且分区固定的环境。在实际操作系统中,为了更高效地管理内存,可能还会采用动态分区、页式或段式等更复杂的内存管理技术。 为了深入理解这些...
TSP属于NP完全问题,没有已知的多项式时间解决方案,因此通常需要借助启发式或近似算法来求解,模拟退火算法就是其中一种常用的方法。 在使用模拟退火算法解决TSP时,通常包含以下几个步骤: 1. **初始化**:设定...
实验结果表明,该算法相比传统的DL方法大大降低了训练和测试阶段的时间复杂度,并且具有较高的识别精度和稳定性。 字典投影学习算法是基于稀疏表示的思想,通过字典学习和投影变换来实现人脸识别。该算法可以有效地...
另外,在语音识别领域,应用动态规划技术的动态时间伸缩算法DTW取得了很大成功,当词汇表较小以及各个词条不易于混淆时,DTW可以有效的解决孤立词识别时说话速度不均匀的难题,从而自20世纪60年代末期掀起了语音识别...
通过阅读和理解这段代码,可以深入学习多资源银行家算法的细节,以及如何在实际编程中应用这种高级操作系统概念。 总结来说,多资源银行家算法是一种预防死锁的有效方法,通过对资源的管理和分配策略,确保系统的...
这种算法的优势在于能处理多目标优化问题,如本文中的任务完成时间和资源负载均衡。 【调度模型】 本文提出了一种基于PSO的云计算任务调度模型。模型中,目标函数包括两个关键指标:任务的【完成时间】和系统的...
在实际应用中,选择GWO还是PSO取决于具体的问题特性、计算资源限制以及对算法性能的需求。理解这两种算法的原理、优缺点以及如何调整参数是优化问题的关键。通过比较和结合不同算法的特性,可以设计出更高效的优化...