Алгоритм проверка списка интервалов

Question

Данного списка значений даты и времени начала/оконечного мне нужно проверить три вещи:

1. для каждого интервала, время начала до конца времени
2. не перекрывается не существует между элементами списка, каждый пуск/конец диапазона должен представлять собой дискретный интервал в общем списке
3. не может быть пробелов в серии, от самого раннего начала до самого последнего конца должен быть непрерывный охват.

Так что, учитывая:

((1970-01-01, 1970-12-31), (1971-01-01, 1971-12-31), (1972-01-01, 1972-12-31), (1973-01-01, 1973-12-31)) 

успешный результат дается.

Учитывая

((1970-12-31, 1970-01-01), (1970-10-01, 1971-12-31), (1972-01-01, 1972-12-31), (1973-01-01, 1973-12-31)) 

сообщение о том, что дата начала наступает после даты окончания в первом элементе обеспечивается.

Учитывая

((1970-01-01, 1970-12-31), (1970-10-01, 1971-12-31), (1972-01-01, 1972-12-31), (1973-01-01, 1973-12-31)) 

сообщение о том, что перекрытие существует между первым и вторым элементами обеспечивается.

Учитывая

((1970-01-01, 1970-12-31), (1971-10-01, 1971-12-31), (1973-01-01, 1973-12-31), (1974-01-01, 1974-12-31)) 

сообщение о том, что существует зазор между вторым и третьим элементами обеспечивается.

Первое требование - это просто, вопрос в том, как лучше всего перевести его на более широкую проверку.

Второе требование в некоторой степени соответствует приведенной ниже статье, но поскольку оно работает только на пару интервалов, я все равно пойму O (n^2), поскольку каждый элемент нужно будет сравнить с любым другим элементом, исправить ? Determine Whether Two Date Ranges Overlap

Эта статья - search for interval overlap in list of intervals? - лучше подходит для второго требования, а первая может быть перенесена в совокупность дерева интервалов.

Так что это оставляет третье требование. Можно ли определить промежутки в общем интервале с использованием дерева интервалов?

Упомянем, что это в Javascript, node.js. Тем не менее, было бы интересно проработать это в Haskell или другом функциональном языке ...

Спасибо!

г/Steve

Answer 1

Этот код обеспечивает решение, хотя я предполагаю, следующее:

• Вы не возражаете список сортируется. Это значительно уменьшает количество сравнений .
• Ваше сравнение между датами в дневном уровне, с учетом ваших примеров. Если нет, вам, вероятно, придется изменить функцию strToDate, а также переменную adjustment.

Идея взята из @alfasin.

var data = [ 
    ['1970-01-01', '1970-12-31'], 
    ['1971-01-01', '1971-12-31'], 
    ['1972-01-01', '1972-12-31'], 
    ['1973-01-01', '1973-12-31'] 
]; 

// comparison is in day level, adjust otherwise. 
var adjustment = 1000 * 60 * 60 * 24; 

var parsedData = []; 
for(var idx = 0; idx < data.length; idx++) { 
    var thisItem = data[idx]; 

    var thisParsedItem = [ 
     Math.floor(strToDate(thisItem[0]).getTime()/adjustment), 
     Math.floor(strToDate(thisItem[1]).getTime()/adjustment), 
     // adding original items here, since I plan to sort the list. 
     thisItem[0], 
     thisItem[1] 
    ]; 

    parsedData.push(thisParsedItem); 
} 

parsedData = parsedData.sort(function (itemA, itemB) { 
    return itemA[0] - itemB[0]; 
}); 


var errorLocation = -1, overlap = false, gap = false, endBeforeStart = false; 
for(var idx = 0; idx < parsedData.length - 1; idx++) { 
    // start before end. 
    if (parsedData[idx][0] > parsedData[idx][1]) { 
     errorLocation = idx; 
     endBeforeStart = true; 
     break; 
    } 

    var d = parsedData[idx + 1][0] - parsedData[idx][1]; 

    // gap. 
    if (d > 1) { 
     errorLocation = idx + 1; 
     gap = true; 
     break; 
    } 

    // overlap. 
    if (d < 1) { 
     errorLocation = idx + 1; 
     overlap = true; 
     break; 
    } 
} 

if (errorLocation > -1) { 
    if (gap) { console.log("You have a gap at: " + errorLocation); } 
    if (overlap) { console.log("You have an overlap at: " + errorLocation); } 
    if (endBeforeStart) { console.log("End before start at: " 
            + errorLocation); } 
} 

function strToDate(input) { 
    var parts = input.split('-'); 
    return new Date(
      parseInt(parts[0]), 
      parseInt(parts[1]), 
      parseInt(parts[2])); 
} 

Answer 2

Анализировать дату первого использования что-то вроде datetime.datetime.strptime в питоне и даты Преобразовать в миллисекунды и делать простые проверки.

Get current time in milliseconds in Python?

Answer 3

без предоставления полного рабочего примера, вы можете сделать следующее:

1. Сортировка списка по дате начала (в функции сортировки вы также можете проверить, если start < end)
2. итерацию в списке и убедитесь, что:
   1. позиция является первым пунктом в списке
   2. дата начала еще один, чем предыдущая дата остановки

Я предполагаю, что это на самом деле не обрушить порядок функции, хотя (N х N журнал N), если он не был уже отсортирован и вам может пропустить шаг 1.