javascript - 时间线间隙检测算法中的错误

Question

我有一个算法可以检查 Event (StartTime,EndTime) 的数组在从 Midnight->Midnight 运行的时间线上检查是否有任何间隙。该算法有效，但有一种配置不起作用。

在我展示代码之前，这里是它不起作用的特定情况:当我有一个午夜结束的事件时，它具有相同的 StartTime。作为另一个不会在午夜结束的事件。这里的问题是我在结果中添加了一个错误的 GAP，GAP (Midnight,Midnight) . 它不应该出现在我的结果中。

现在代码:所有事件(包括 GAP 事件)都有一个 (StartTime,EndTime) .我收到一个正常的传入数组 proposedEvents ，我的工作是返回一个填充的数组 preparedGapEvents .

function schedulerPrepareGapEvents(proposedEvents) {

var preparedGapEvents = [];

// First sort proposed events by StartTime
proposedEvents.sort(sortObjectsByStartTime); // sort by StartTime of the event

// If there are no proposed events, exit immediately with an empty result
if (proposedEvents.length == 0) {
    return preparedGapEvents;
}   

// Manually add first gap, if it exists: Sorted Proposed Event #1 not starting at 12:00am
var startTimeFirst = getTimestampFromString(proposedEvents[0].startTime);
if (startTimeFirst > 0) {
    preparedGapEvents.push({"gapEventID" : "event-GAP" + generateUniqueID(), 
                            "gapEventColor" : globalGapEventColor, 
                            "gapEventStartTimestamp" : 0, 
                            "gapEventEndTimestamp" : startTimeFirst});      
}

// Initially lastMaxEndTime is the End Time of 1st Event
var lastMaxEndTime = getTimestampFromString(proposedEvents[0].endTime); 

// Main Event Traversal Loop
jQuery.each(proposedEvents, function(index, item) {     

    // Get the current proposed event's StartTime/EndTime in the loop
    var startTimeCurrent = getTimestampFromString(item.startTime);
    var endTimeCurrent = getTimestampFromString(item.endTime);

    // Next neighboring proposed event
    var nextEvent = proposedEvents[index+1];

    // If Next Proposed Event exists
    if (nextEvent != null) {
        var startTimeNext = getTimestampFromString(nextEvent.startTime);
        var endTimeNext = getTimestampFromString(nextEvent.endTime);

        if (startTimeNext > lastMaxEndTime) { // Gap detected! 
            preparedGapEvents.push({"gapEventID" : "event-GAP" + generateUniqueID(), 
                                    "gapEventColor" : globalGapEventColor,
                                    "gapEventStartTimestamp" : lastMaxEndTime, 
                                    "gapEventEndTimestamp" : startTimeNext});               
        }

        // Keep track of the current MAX EndTime: either this new event's EndTime or the previous Max EndTime
        lastMaxEndTime = Math.max(lastMaxEndTime, endTimeNext);
    }
    else {
        // Last Proposed Event (no next neighbor): its End Time must be at the 24-hr END mark, otherwise a gap
        if (endTimeCurrent < 1440) {
            preparedGapEvents.push({"gapEventID" : "event-GAP" + generateUniqueID(), 
                                    "gapEventColor" : globalGapEventColor,
                                    "gapEventStartTimestamp" : lastMaxEndTime, 
                                    "gapEventEndTimestamp" : 1440});
        }
    }
}); 

return preparedGapEvents;

这里的问题出在主循环的某个地方。在我按 StartTime 排序后，两个相邻的事件可以在位置 0 或 1，取决于机会。假设我碰巧有一个邻居处于我要检查的 +1 位置。那样的话，我就落入了ELSE，满足条件if (endTimeCurrent < 1440)因为该事件的结束时间不是 1440(午夜)!

那么我该如何解决这个问题呢？

Answer 1

这是我的理解-

1. 24 小时窗口中有“事件”。

2. 事件有开始时间和结束时间。

3. 如果没有事件，则为“GAP”。

4. “GAP”也被视为事件。

5. 可以有并发事件(根据您提供的图表至少有两个)。

6. 关于位置“0”和“1”，我假设它们指的是您问题中图中的蓝色和红色部分。

问题陈述是您正在尝试识别“GAP”时间并将它们列出来。你已经建立了上面的算法来做到这一点。根据我收集到的信息，它(识别差距)不适用于并发事件(在其中一个位置)，因为没有处理重叠。

处理重叠事件的一种方法如下 - 确定哪些事件的持续时间更短并删除该事件。

也不清楚为什么您将 1440 视为午夜。它指的是下午 2:20，不是吗？

问候，

拉文德拉