logo标签列表

寻找重叠事件/时间的算法

javascriptjqueryalgorithm
6
在制作自定义日历时，我无法确定如何找到与任何其他时间段重叠的时间段。
时间段从0到720开始（9am至9pm，每个像素代表一分钟）。
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（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到10有3个事件，时间段6到7有2个事件。
我创建了以下公式来将时间数字转换为实际时间：
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 if you need.

也许你只是对jquery-week-calendar (https://github.com/themouette/jquery-week-calendar) 感兴趣。 - user57508
最近，我写了一个JavaScript函数来查找所有不重叠的区间组合。这个函数是你需要的吗？ - Anderson Green
3个回答
7
从我的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;

所以...你不愿意为解决你自己的问题提供一些自己的精力...好吧。

(Note: I kept the HTML tags as requested.)
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);
    });
});
我不知道如何使用它，你可以用提供的数据来使用吗？ - Dev555
@Dev555 添加了一些改编后的演示代码（但是，你必须自行适应分组组织！） - user57508
@Dev555 请阅读我的评论：（但是，你必须自己适应组织！） - user57508
1
@Dev555 即使你是一个...不错的人...我已经调整了我的回答 - 但我强烈建议你改善你的态度！ - user57508
谢谢，其实我自己想不出来，否则我就自己做了 :) 检查中... - Dev555
5

对我来说，使用每个开始和结束事件的时间戳更容易，这样您可以直接使用它们或将它们更改为日期对象。要获取值，请为每个开始和结束创建一个日期对象，然后：

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年5月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
谢谢，但您能否修改以适应我的数据，或者您是如何创建每个时间段的日期对象的？ - Dev555
1

这里是可以实现你想要的功能的代码。正如其他人所提到的，存储日期对象可能会更好，但那是另一个问题。

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;
}
@AndreasNiedermair：我认为你的测试用例是失败还是期望行为取决于解释。然而，原帖作者应该考虑如何处理这些边缘情况。 - Programming Guy
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接