Поиск пересечений отрезков (времени) в массивах - Разбор алгоритмической задачи с собеседований PHP

Задача:
Даны два списка отрезков времени, каждый список упорядочен.

Найдите третий список, в котором будут отрезки, являющиеся пересечениями первых двух списков.

Например для:

[[1, 5], [7, 10], [12, 24]]
[[4, 6], [12, 13], [30, 35]]

Ответом будет:

[[4, 5], [10, 12]]

Разбор решения

В решении будем применять визуализацию:

-------    ----------         ------------        -----       -----
   ------     ---   ------  -----       -------           --          -----  --------

(в процессе решения)

<?php

$a = [[1, 5], [7, 10], [12, 24]];

$b = [[4, 6], [12, 13], [30, 35]];



print_r(getIntersectIntervals($a, $b));

function getIntersectIntervals(array $a, array $b): array {
    $result = [];
    $bCount = count($b);
    $start = 0;
    foreach($a as $interval) { // будем перебирать весь массив, л
        for ($i = $start; $i < $bCount; $i++) {
            [$intersect, $has_second_something_in_future] = getIntersect($interval[0], $interval[1], $b[$i][0], $b[$i][1]);
            if (!empty($intersect)) {
                $result[] = $intersect;
            }
            // if (!$has_second_something_in_future) {
            //     $start++;
            // }
        }
    }
    return $result;
}

function  getIntersect(int $a, int $b, int $c, int $d): array {
    $instersect = [];
    $left = $a > $c ? $a : $c;
    $has_second_something_in_future = $d > $b;
    $right = $has_second_something_in_future ? $b : $d;

    $instersect = $left <= $right ? [$left, $right] : [];
    return [$instersect, $has_second_something_in_future];
}

Далее проведем пару оптимизаций:

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

<?php
 
$a = [[1, 5], [7, 10], [12, 24]];
 
$b = [[4, 6], [12, 13], [30, 35]];
/**
 * Визуализируем это условие:
 * ------  ------     -------
 *    ----          ----       ----
 */
 
 
print_r(getIntersectIntervals($a, $b));
 
function getIntersectIntervals(array $a, array $b): array {
    $result = [];
    $bCount = count($b);
    $start = 0;
    $count = 0;
    foreach($a as $interval) { // будем перебирать весь массив, л
        for ($i = $start; $i < $bCount; $i++) {
            $count++; // посчитаем количество сравнений
            [$intersect, $has_second_something_in_future] = getIntersect($interval[0], $interval[1], $b[$i][0], $b[$i][1]);
            if (!empty($intersect)) {
                $result[] = $intersect;
            }
             // сдвигаем старт во втором массиве
            if (!$has_second_something_in_future) {
                $start++;
            } /*
            Если пересечения нет, но очередной отрезок второго массива целиком в будущем,
            то смысла досматривать второй массив для текущего элемента первого нет
            */
            else if (empty($intersect)) {
                break;
            }
        }
    }
    return [$result, $count];
}
 
function  getIntersect(int $a, int $b, int $c, int $d): array {
    $instersect = [];
    $left = $a > $c ? $a : $c;
    $has_second_something_in_future = $d > $b;
    $right = $has_second_something_in_future ? $b : $d;
 
    $instersect = $left <= $right ? [$left, $right] : [];
    return [$instersect, $has_second_something_in_future];
}

Видео-материалы

• Поиск пересечений отрезков (времени) из двух массивов - Разбор алгоритмической задачи с Собеседования (2025): Ютуб | ВкВидео | Телеграм

Допонительные материалы

• Разбор решения этой же задачи с другой структурой кода на Golang: https://fkn.ktu10.com/?q=node/17600