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

Условие

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

intersection( [[8, 12], [17, 22]], [[5, 11], [14, 18], [20, 23]] )// [[8, 11], [17, 18], [20, 22]]

intersection( [[9, 15], [18, 21]], [[10, 14], [21, 22]] )// [[10, 14]]

function intersection(user1, user2) { // your code here }

Ответ

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

Пример решения на JavaScript:

function intersection(user1, user2) {
  let i = 0, j = 0;
  const result = [];

  while (i < user1.length && j < user2.length) {
    const start = Math.max(user1[i][0], user2[j][0]);
    const end = Math.min(user1[i][1], user2[j][1]);

    if (start < end) { // есть пересечение
      result.push([start, end]);
    }

    // сдвигаем указатель у того интервала, который заканчивается раньше
    if (user1[i][1] < user2[j][1]) {
      i++;
    } else {
      j++;
    }
  }

  return result;
}

// Пример использования:
console.log(intersection(
  [[8, 12], [17, 22]],
  [[5, 11], [14, 18], [20, 23]]
));
// Выведет: [[8, 11], [17, 18], [20, 22]]

Этот алгоритм работает за время O(n + m), где n и m — длины списков интервалов.