代码之家 › 专栏 › 技术社区 › gene b.

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

sorting algorithm javascript

gene b. · 技术社区 · 6 年前

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

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

现在的代码是:所有事件(包括间隙事件)都有 (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;

这里的问题在主循环的某个地方。在我排序之后 开始时间 ,两个相邻事件可以位于位置0或1, 取决于机会 . 假设碰巧有一个邻居在我要检查的+1位置。在这种情况下,我落入ELSE,并满足条件 if (endTimeCurrent < 1440) 因为该活动的结束时间不是1440(午夜)!

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

0 回复 | 直到 6 年前

Ravindra HV 6 年前

这就是我所理解的-

24小时窗口中有“事件”。
事件有开始时间和结束时间。
如果没有事件,则为“间隙”。
“间隙”也被视为一个事件。
可以有并发事件(从您给出的图中至少有两个)。
关于位置“0”和“1”,我假设它们指的是您问题中图中的蓝色和红色部分。

问题是,你试图找出“间隙”时间并将其列出。您已经构建了上述算法来实现这一点。从我收集的信息来看,它(间隙识别)不适用于并发事件(在其中一个位置),因为重叠没有得到处理。

处理重叠事件的一种方法如下所示-确定哪些事件的持续时间较小,并删除该事件。

也不清楚为什么你认为1440年是午夜。指的是下午2点20分,不是吗?

当做

拉温德拉

grodzi 6 年前

我定义了 task 作为(具有 start 日期和an end 日期)
我 重新定义 一 event 作为发生的事情:任务开始或结束

您可能想做的是沿着t旅行,并对您的事件相应地(无论是开始任务还是结束任务)

考虑以下时间表

---------------->t
 O----X
   O-----X
   O------------X

其中O代表开始任务,X代表结束任务

这与检查html是否有效非常相似:如果您遇到一个开始标记,但目前没有开始标记,那么您就有一个间隙。

所以算法如下:

events = []
forall tasks as start, end:
    events.push({start: true, at: start}, {start:false, at:end})

sort the events as:
    first by t time
    in case two events have the same t,
    opening events should come before closing ones
forall events:
    when a start task: 
        if openTagCounter == 0 //and different than init
            gaps.push(lastClosedAt, task.start)
        openTagCounter++
    when a end task:
        openTagCounter--
        if openTagCounter == 0
            lastClosedAt = task.end

您可以在开始和开始时处理最终的差距

if startDay < events[0].start
    gaps.push(guess what)
if last(events).end < endDay
    gaps.push(same)

function getGaps(startDay, endDay, tasks){
    let events = tasks.flatMap(t=>{
        return [{ref: t, at: t.start, start:true},{ref: t, at: t.end, start:false}]
    },[]);

    events.sort((a,b)=>{
        if(a.at!=b.at) return a.at-b.at;
        return a.start?-1:0;
    });

    let gaps = [];
    let lastClosed = 0;//lastClosed only truthy if start of a gap
    let anyOpened = 0;
    events.forEach(ev=>{
        if(ev.start){
            anyOpened++;
            if(lastClosed){
                gaps.push({start: lastClosed, end: ev.at});
                lastClosed = false;
            }
        }else{
            anyOpened--;
            if(anyOpened == 0){
                lastClosed = ev.at;
            }
        }
    });

    //finally handle the first gap, and the last gap
    if(startDay != events[0].at){
        gaps.push({start: startDay, end: events[0].at})
    }
    if(endDay != events[events.length-1].at){
        gaps.push({start: events[events.length-1].at, end: endDay})   
    }
    return gaps;
}
console.log(getGaps(0, 24, [
    {start:23, end:23.5},
    {start:23, end:24},
]))
//[ { start: 0, end: 23 } ]
console.log(getGaps(0, 24, [
    {start:23, end:24},
    {start:23, end:23.5},
]))
//[ { start: 0, end: 23 } ]
console.log(getGaps(0, 24, [
    {start:23, end:23.7},
    {start:23, end:23.5},
]))
//[ { start: 0, end: 23 }, { start: 23.7, end: 24 } ]
console.log(getGaps(0, 24, [
    {start:23, end:23.5},
    {start:23.5, end:23.7},
    {start:23, end:23.5},
    {start:23.5, end:23.7},
]))
//[ { start: 0, end: 23 }, { start: 23.7, end: 24 } ]

Trentium 6 年前

这是另一个镜头。。。它简化了 schedulerPrepareGapEvents 仅通过检查 startTime 大于 lastMaxEndTime ,并相应地添加间隙。然后,循环完成后,函数只需检查两个循环之间是否存在间隙 lastMaxEndTime 午夜(1440分钟)。

// Filler functions to support testing...
var uid = 1;
function generateUniqueID() { return uid++};
function getTimestampFromString(x) {return x};
var globalGapEventColor = 123;

// Function to seek gaps between events.
function schedulerPrepareGapEvents(proposedEvents) {

  // First sort proposed events by StartTime
  proposedEvents.sort((a, b) => getTimestampFromString(a.startTime) - getTimestampFromString(b.startTime)); // sort by StartTime of the event

  // Initialize lastMaxEndTime to the beginning of the time interval
  var lastMaxEndTime = 0;
  var preparedGapEvents = [];

  // Main Event Traversal Loop
  for (var index = 0; index < proposedEvents.length; index++) {

    var item = proposedEvents[index];

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

    // If the startTime is greater than the last max end time, add as a gap.
    if (lastMaxEndTime < startTimeCurrent) { // Gap detected! 
        preparedGapEvents.push({"gapEventID" : "event-GAP" + generateUniqueID(), 
                                "gapEventColor" : globalGapEventColor,
                                "gapEventStartTimestamp" : lastMaxEndTime, 
                                "gapEventEndTimestamp" : startTimeCurrent});               
    }

    lastMaxEndTime = Math.max(lastMaxEndTime, endTimeCurrent);
  }

  // Finally, add any gap up to midnight.
  if (lastMaxEndTime < 1440) {
      preparedGapEvents.push({"gapEventID" : "event-GAP" + generateUniqueID(), 
                              "gapEventColor" : globalGapEventColor,
                              "gapEventStartTimestamp" : lastMaxEndTime, 
                              "gapEventEndTimestamp" : 1440});
  }
        
  return preparedGapEvents;
}

// Run test...
console.log("Test 1:");
var pe0 = [{startTime: 22*60, endTime: 24*60}, {startTime: 22*60, endTime: 23*60}];
console.log( schedulerPrepareGapEvents( pe0 ) );

console.log("Test 2:");
var pe1 = [{startTime: 22*60, endTime: 23*60}, {startTime: 22*60, endTime: 24*60}];
console.log( schedulerPrepareGapEvents( pe1 ) );

希望这有帮助。。。