算法找出重叠的事件/次 [英] Algorithm for finding overlapping events/times

问题描述

当处理自定义日历，我无法弄清楚如何找到时段重叠任何其他时隙。

While working on custom calendar, I can't figure out how to find time slots that overlaps any other time slot.

时隙开始从0到720（上午9点至晚上9点的每个像素再presenting一分钟的）。

Time slots start from 0 to 720 (9am to 9pm with each pixel representing a minute).

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等。

Each time slots is of one hour, for example 9 to 10, 10 to 11, 11 to 12 and so on.

在上面的例子中，三个事件（ID：1,2,3）重叠的 9-10 的启动的时间： 9:00 ， 9:30 和 9:20 。和其他活动的重叠是 6 INT时隙 7 （ID：5，6） 6 和 6:20 的启动的时间。 ID为事件 4 没有在时隙任何重叠事件12 到 1 。

In the above example, three events (id: 1,2,3) are overlapping for the 9-10 start time: 9:00, 9:30 and 9:20. And other events overlapping are int time slot of 6 to 7 (id: 5, 6) with 6 and 6:20 start times. The event with id 4 doesn't have any overlapping events in the time slot of 12 to 1.

我要寻找一种方式来获得所有重叠的事件ID的事件，以及一些在特定的时间段，这是预期的输出：

I am looking for a way to get all overlapping event ids as well as number of events in a particular time slot, this is expected output:

[
 {id:1, eventCount: 3},
 {id:2, eventCount: 3},
 {id:3, eventCount: 3},
 {id:5, eventCount: 2},
 {id:6, eventCount: 2}
]

有关IDS（1〜3），有 3 的时隙 9 事件 10 和 2 的时隙 6 到 7 。

For ids (1 to 3), there are 3 events for time slot 9 to 10 and 2 events for time slot 6 to 7.

我已经创造了这个公式的时间数字转换为实际时间：

I have created this formula to convert time number to actual time:

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
   }
}

DEMO，如果您需要。

推荐答案

这是我的<一个href="https://github.com/dittodhole/jquery-week-calendar/commit/6dbf12cca6024f37f964ea825c25b831f3983c1d"相对=nofollow> jQuery的周历提交，这就是我如何做到这一点：

from my jquery-week-calendar commit, this is how i do it:

    _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;
    }

有位组件特定的噪音身边，但你会得到的逻辑：

there's a bit of component-specific noise around, but you'll get the logic:

• 排序他们的首发事件上升
• 排序他们的结局的事件上升
• 遍历排序的事件，并检查previous事件的开始/结束（完成而按位置，不是由事件属性自理 - 只是因为设计可能会重叠，但事件不...例如：使边界2px的，有没有重叠的起始/终止时间的事件可能会重叠或碰）
• 每个交叠组（ currentGroup ）里面的组一个新的数组 -array

• sort the events by their starting ascending
• sort the events by their ending ascending
• iterate over the sorted events and check the starting/ending of the previous event (done rather by position, than by the event properties themself - just because the design might overlap, but the events not ... eg: making a border 2px, events with not overlapping start/end-times might overlap or "touch")
• each overlapping-group (currentGroup) is a new array inside the groups-array

洙...你$ C​​ $ C看起来事物都这样（顺便说一句，没有必要与现实最新工作 -instances）

soo ... your code might look sth alike this (btw, no need to work with the real date-instances)

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;

洙......你是不是有决心推动一些自己的精力投入到的您的问题......好吧

soo ... you are not willed to push some own energy into your problem ... well

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

这篇关于算法找出重叠的事件/次的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！