Задача: 56. Merge Intervals
Сложность: medium

Дан массив интервалов, где intervals[i] = [starti, endi]. Объедините все перекрывающиеся интервалы и верните массив неперекрывающихся интервалов, которые покрывают все интервалы во входных данных.

Пример:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

👨‍💻 Алгоритм:

1⃣ Представление графа:
Имея представленную интуицию, мы можем изобразить граф в виде списка смежности, вставляя направленные ребра в обоих направлениях, чтобы симулировать неориентированные ребра.

2⃣Определение компонент связности:
Для определения, в какой компоненте связности находится каждый узел, мы выполняем обходы графа от произвольных непосещенных узлов до тех пор, пока все узлы не будут посещены. Для эффективности мы храним посещенные узлы в множестве (Set), что позволяет проводить проверки на принадлежность и вставку за константное время.

3⃣Объединение интервалов внутри компонент:
Наконец, мы рассматриваем каждую связную компоненту, объединяя все её интервалы, создавая новый интервал с началом, равным минимальному началу среди всех интервалов в компоненте, и концом, равным максимальному концу.

Решение:

class Solution {
    private $graph = [];
    private $nodesInComp = [];
    private $visited = [];

    private function overlap($a, $b) {
        return $a[0] <= $b[1] && $b[0] <= $a[1];
    }

    private function buildGraph($intervals) {
        foreach ($intervals as $interval1) {
            foreach ($intervals as $interval2) {
                if ($this->overlap($interval1, $interval2)) {
                    $this->graph[serialize($interval1)][] = $interval2;
                    $this->graph[serialize($interval2)][] = $interval1;
                }
            }
        }
    }

    private function mergeNodes($nodes) {
        $minStart = $nodes[0][0];
        $maxEnd = $nodes[0][1];
        foreach ($nodes as $node) {
            $minStart = min($minStart, $node[0]);
            $maxEnd = max($maxEnd, $node[1]);
        }
        return [$minStart, $maxEnd];
    }

    private function markComponentDFS($start, $compNumber) {
        $stack = [];
        array_push($stack, $start);
        while (!empty($stack)) {
            $node = array_pop($stack);
            if (!in_array($node, $this->visited, true)) {
                $this->visited[] = $node;
                $this->nodesInComp[$compNumber][] = $node;
                foreach ($this->graph[serialize($node)] as $child) {
                    array_push($stack, $child);
                }
            }
        }
    }

    private function buildComponents($intervals) {
        $compNumber = 0;
        foreach ($intervals as $interval) {
            if (!in_array($interval, $this->visited, true)) {
                $this->markComponentDFS($interval, $compNumber);
                $compNumber++;
            }
        }
    }

    public function merge($intervals) {
        $this->buildGraph($intervals);
        $this->buildComponents($intervals);
        $merged = [];
        foreach ($this->nodesInComp as $components) {
            $merged[] = $this->mergeNodes($components);
        }
        return $merged;
    }
}

Ставь 👍 и забирай 📚 Базу знаний