JSFiddle - React, Tailwind, and code Playground

by Valentin Sarychev

HTML

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/3.10.0/lodash.min.js"></script>
<pre id="output"></pre>

JavaScript

// Интервал
function Span(start, end) {
    this.start = start;
    this.end = end;
}

// Возвращает true, интервал попадает внутрь отрезка span
Span.prototype.isVisible = function(span) {
    return (span.start - this.start) * (span.end - this.start) <= 0
        || (span.start - this.end) * (span.end - this.end) <= 0;
};

// 30к случайных временных интервалов
var spans = new Array(30000);
for (var i = 0; i < spans.length; ++i) {
    var start = Math.random() * 1000;
    var length = Math.random() * 100;
    spans[i] = new Span(new Date(start), new Date(start + length));
}

// видимый диапазон отрезков
var visibleSpan = new Span(new Date(700), new Date(702));

var calcStart = new Date();

// рассчитать количество отрезков попадающих в видимый интервал
var intersectedCount = 0;
for (i = 0; i < spans.length; ++i) {
    intersectedCount += spans[i].isVisible(visibleSpan);
}

var calcEnd = new Date();

document.getElementById('output').innerText = 'Нашли видимые интервалы полным перебором за ' + (calcEnd - calcStart) + 'мс. ' + intersectedCount + '/' + spans.length + ' видимых.';

//===========================================================
// Более производительный способ получения видимых интервалов
//===========================================================

// Подоготовим заранее специальный отсортированный массив интервалов
var sortedSpanArr = [];
spans.forEach(function(span) {
    sortedSpanArr.push({key: span.start, value: span});
    sortedSpanArr.push({key: span.end, value: span});
});
sortedSpanArr.sort(function(a, b) {
    return a.key - b.key;
});

calcStart = new Date();

// и бинарным поиском будем находить видимые интервалы
var from = _.sortedIndex(sortedSpanArr, {key: visibleSpan.start, value: visibleSpan}, function(x) {
    return x.key;
});
var to = _.sortedLastIndex(sortedSpanArr, {key: visibleSpan.end, value: visibleSpan}, function(x) {
    return x.key;
});
intersectedCount = _(sortedSpanArr).slice(from, to).map(function(x) {
    return...