Пересечения интервалов онлайна

Задача

Даны два отсортированных списка с интервалами присутствия пользователей в онлайне в течение дня. Начало интервала строго меньше конца. Нужно вычислить интервалы, когда оба пользователя были в онлайне. Интервалы указаны в часах, считаем что могут быть часы от 0 до 24.

Пример

console.log(
    getIntersections(
        [[8, 12], [17, 22]],
        [[5, 11], [14, 18], [20, 23]]
    )
); // [8, 11], [17, 18], [20, 22]
 
console.log(
    getIntersections(
        [[9, 15], [18, 21]],
        [[10, 14], [21, 22]]
    )
); // [10, 14]
 
console.log(
    getIntersections(
        [[10, 14], [21, 24]],
        [[9, 15], [18, 21], [22, 24]]
    )
); // [10, 14], [22, 24]

Решение

Оптимальное решение

// Временная сложность: O(n + m), где n и m — длины массивов.
// Пространственная: O(n + m)
 
function getIntersections(user1, user2) {
    const result = [];
    let i = 0;
    let j = 0;
 
    while (i < user1.length && j < user2.length) {
        // Извлекаем начало и конец для текущих интервалов
        const [start1, end1] = user1[i];
        const [start2, end2] = user2[j];
 
        // Вычисляем границы пересечения
        // Начало общего интервала - это максимум из начал
        const intersectionStart = Math.max(start1, start2);
        // Конец общего интервала - это минимум из концов
        const intersectionEnd = Math.min(end1, end2);
 
        // Если начало строго меньше конца, значит пересечение есть
        if (intersectionStart < intersectionEnd) {
            result.push([intersectionStart, intersectionEnd]);
        }
 
        // Двигаем указатель того интервала, который заканчивается раньше.
        // Тот, что заканчивается позже, может пересечься со следующим интервалом другого списка.
        if (end1 < end2) {
            i++;
        } else {
            j++;
        }
    }
 
    return result;
}

См. также

• find-max-count
• two-pointers (паттерн)