Ошибка в алгоритме обнаружения пробелов на временной шкале

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

• Я определяю task как (то, что имеет дату start и end дату)
• I переопределить 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 } ]

Answer 2

Вот еще один вариант ... Он упрощает основной цикл функции 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 ) );

Надеюсь, это поможет ...

Answer 3

Это то, что я понял -

1. В 24-часовом окне есть «события».

2. События имеют время начала и время окончания.

3. Если нет событий, то это 'GAP'.

4. «GAP» также считается событием.

5. Возможны одновременные события (два по крайней мере из диаграммы, которую вы дали).

6. Что касается позиций «0» и «1», я предполагаю, что они относятся к сине-красной секции на рисунке в вашем вопросе.

Проблема заключается в том, что вы пытаетесь определить время 'GAP' и вывести его в список. Вы использовали вышеупомянутый алгоритм, чтобы сделать это. Из того, что я собрал, он (идентификация пробелов) не работает для одновременных событий (в одной из позиций), поскольку перекрытие не обрабатывается.

Один из способов обработки перекрывающихся событий будет следующим:определите, какие из событий имеют меньшую продолжительность, и удалите это событие.

Также неясно, почему вы рассматриваете 1440 как полночь. Это относится к 14:20, не так ли?

С уважением,

Равиндра