用于查找重叠事件/时间的算法
Algorithm for finding overlapping events/times
在自定义日历上工作时,我不知道如何找到与任何其他时间段重叠的时间段。
时隙从 0 到 720(上午 9 点到晚上 9 点,每个像素代表一分钟(。
var events = [
{id : 1, start : 0, end : 40}, // an event from 9:00am to 9:40am
{id : 2, start : 30, end : 150}, // an event from 9:30am to 11:30am
{id : 3, start : 20, end : 180}, // an event from 9:20am to 12:00am
{id : 4, start : 200, end : 230}, // an event from 12:20pm to 12:30pm
{id : 5, start : 540, end : 600}, // an event from 6pm to 7pm
{id : 6, start : 560, end : 620} // an event from 6:20pm to 7:20pm
];
每个时间段为一小时,例如 9 到 10、10 到 11、11 到 12 等。
在上面的示例中,三个事件(id:1,2,3(在9-10
开始时间重叠:9:00
、9:30
和9:20
。其他重叠的事件是 6
到 7
的 int 时隙(id: 5, 6(,6
和6:20
开始时间。ID 为 4
的事件在12
1
的时隙中没有任何重叠事件。
我正在寻找一种方法来获取所有重叠的事件 ID 以及特定时间段中的事件数量,这是预期的输出:
[
{id:1, eventCount: 3},
{id:2, eventCount: 3},
{id:3, eventCount: 3},
{id:5, eventCount: 2},
{id:6, eventCount: 2}
]
对于 id(1 到 3(,时隙9
有3
事件到10
,时隙6
有2
事件到7
。
我创建了这个公式来将时间数字转换为实际时间:
var start_time = new Date(0, 0, 0, Math.abs(events[i].start / 60) + 9, Math.abs(events[i].start % 60)).toLocaleTimeString(),
var end_time = new Date(0, 0, 0, Math.abs(events[i].end / 60) + 9, Math.abs(events[i].end % 60)).toLocaleTimeString();
这是我到目前为止所拥有的:
function getOverlaps(events) {
// sort events
events.sort(function(a,b){return a.start - b.start;});
for (var i = 0, l = events.length; i < l; i++) {
// cant figure out what should be next
}
}
如果需要,可以演示。
来自我的 jquery-week-calendar 提交,这就是我的做法:
_groupOverlappingEventElements: function($weekDay) {
var $events = $weekDay.find('.wc-cal-event:visible');
var complexEvents = jQuery.map($events, function (element, index) {
var $event = $(element);
var position = $event.position();
var height = $event.height();
var calEvent = $event.data('calEvent');
var complexEvent = {
'event': $event,
'calEvent': calEvent,
'top': position.top,
'bottom': position.top + height
};
return complexEvent;
}).sort(function (a, b) {
var result = a.top - b.top;
if (result) {
return result;
}
return a.bottom - b.bottom;
});
var groups = new Array();
var currentGroup;
var lastBottom = -1;
jQuery.each(complexEvents, function (index, element) {
var complexEvent = element;
var $event = complexEvent.event;
var top = complexEvent.top;
var bottom = complexEvent.bottom;
if (!currentGroup || lastBottom < top) {
currentGroup = new Array();
groups.push(currentGroup);
}
currentGroup.push($event);
lastBottom = Math.max(lastBottom, bottom);
});
return groups;
}
周围有一些特定于组件的噪音,但你会得到逻辑:
- 按事件的起始升序对事件进行排序
- 按事件结尾升序对事件进行排序
- 迭代排序的事件并检查上一个事件的开始/结束(而不是按位置完成,而不是按事件属性本身完成 - 只是因为设计可能重叠,但事件不是......例如:将边框设为 2px,开始/结束时间不重叠的事件可能会重叠或"触摸"(
- 每个重叠组(
currentGroup
(是groups
数组内的新数组
所以。。。您的代码可能与此类似(顺便说一句,无需使用真实的date
实例(
events.sort(function (a, b) {
var result = a.start - b.start;
if (result) {
return result;
}
return a.end - b.end;
});
var groups = new Array();
var currentGroup;
var lastEnd = -1;
jQuery.each(events, function (index, element) {
var event = element;
var start = event.start;
var end = event.end;
if (!currentGroup || lastEnd < start) {
currentGroup = new Array();
groups.push(currentGroup);
}
currentGroup.push(event);
lastEnd = Math.max(lastEnd, end);
});
return groups;
所以。。。你不愿意把自己的一些精力投入到你的问题上......井
var output = new Array();
jQuery.each(groups, function (index, element) {
var group = element;
if (group.length <= 1) {
return;
}
jQuery.each(group, function (index, element) {
var event = element;
var foo = {
'id': event.id,
'eventCount': group.length
};
output.push(foo);
});
});
,为每个开始和结束事件使用时间戳更容易,这样您就可以直接使用它们或将它们更改为日期对象。若要获取该值,请为每个开始和结束创建一个日期对象,然后:
var a.start = startDate.getTime();
var a.end = endDate.getTime();
对于重叠:
if (a.start <= b.start && a.end > b.start ||
a.start < b.end && a.end >= b.end) {
// a overlaps b
}
如果您愿意,您可以将它们保留为日期对象,上述内容也可以正常工作。
编辑
好的,这是一个工作示例:
假设标称日期为 2012-05-15,则事件数组如下所示:
// Use iso8601 like datestring to make a local date object
function getDateObj(s) {
var bits = s.split(/[- :]/);
var date = new Date(bits[0], bits[1] - 1, bits[2]);
date.setHours(bits[3], bits[4], 0);
return date;
}
var events = [
{id: 1, start: getDateObj('2012-05-15 09:00'), end: getDateObj('2012-05-15 09:30')},
{id: 2, start: getDateObj('2012-05-15 09:30'), end: getDateObj('2012-05-15 11:30')},
{id: 3, start: getDateObj('2012-05-15 09:20'), end: getDateObj('2012-05-15 12:00')},
{id: 4, start: getDateObj('2012-05-15 12:20'), end: getDateObj('2012-05-15 12:30')},
{id: 5, start: getDateObj('2012-05-15 18:00'), end: getDateObj('2012-05-15 19:00')},
{id: 6, start: getDateObj('2012-05-15 18:20'), end: getDateObj('2012-05-15 19:20')}
];
function getOverlappingEvents(eventArray) {
var result = [];
var a, b;
// Sort the event array on start time
eventArray.sort(function(a, b) {
return a.start - b.start;
});
// Get overlapping events
for (var i=0, iLen=eventArray.length - 1; i<iLen; i++) {
a = eventArray[i];
b = eventArray[i + 1];
if ((a.start <= b.start && a.end > b.start) ||
(a.start < b.end && a.end >= b.end) ) {
result.push([a.id, b.id]);
}
}
return result;
}
// Run it
alert(getOverlappingEvents(events).join(''n')); // 1,3 2,3 5,6
这是可以执行所需操作的代码。正如其他人提到的,存储日期对象可能会更好地为您服务,但这是一个不同的问题。
function getOverlaps(events) {
// sort events
events.sort(function (a, b) {
return a.start - b.start;
});
var results = [];
for (var i = 0, l = events.length; i < l; i++) {
var oEvent = events[i];
var nOverlaps = 0;
for (var j = 0; j < l; j++) {
var oCompareEvent = events[j];
if (oCompareEvent.start <= oEvent.end && oCompareEvent.end > oEvent.start || oCompareEvent.end <= oEvent.start && oCompareEvent.start > oEvent.end) {
nOverlaps++;
}
}
if (nOverlaps > 1) {
results.push({
id: oEvent.id,
eventCount: nOverlaps,
toString: function () {
return "[id:" + this.id + ", events:" + this.eventCount + "]"
}
});
}
}
return results;
}
- Java脚本时间添加
- Json数据包含日期和时间格式
- 如何根据时间运行不同的脚本
- 用每小时的差值填充数组/列表-从下拉列表中给定两个时间值
- 循环比赛位置算法
- 在wordpress一定时间后更改自定义字段
- javascript扫雷器floodfill算法不能正常工作
- 更改angularjs中的日期-时间格式
- 将当前时间添加到我的页面上的特定部分
- 门户网站:当地时间有多有用
- 显示时间的脚本
- 如何在窗体打开时从javascript倒计时计时器值中节省时间
- 通过JSON&比较时间
- 用于查找基于时间的事件的最佳Javascript算法
- 用于查找重叠事件/时间的算法
- 这个算法的时间复杂度是多少
- 时间计算算法
- 排序算法的时间复杂度应该是多少
- 基于标签使用频率和最后使用时间的标签自动补全排序算法
- 显示打开时间算法javascript