Swift | LeetCode

Задача: 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⃣Объединение интервалов внутри компонент:
Наконец, мы рассматриваем каждую связную компоненту, объединяя все её интервалы, создавая новый интервал с началом, равным минимальному началу среди всех интервалов в компоненте, и концом, равным максимальному концу.

😎

Решение:

import Foundation

class Solution {
    var graph = [Array<Int>: [[Int]]]()
    var nodesInComp = [Int: [[Int]]]()
    var visited = Set<Array<Int>>()

    func overlap(_ a: [Int], _ b: [Int]) -> Bool {
        return a[0] <= b[1] && b[0] <= a[1]
    }

    func buildGraph(_ intervals: [[Int]]) {
        for interval1 in intervals {
            for interval2 in intervals {
                if overlap(interval1, interval2) {
                    graph[interval1, default: []].append(interval2)
                    graph[interval2, default: []].append(interval1)
                }
            }
        }
    }

    func mergeNodes(_ nodes: [[Int]]) -> [Int] {
        var minStart = nodes[0][0]
        for node in nodes {
            minStart = min(minStart, node[0])
        }

        var maxEnd = nodes[0][1]
        for node in nodes {
            maxEnd = max(maxEnd, node[1])
        }

        return [minStart, maxEnd]
    }

    func markComponentDFS(_ start: [Int], _ compNumber: Int) {
        var stack = [[Int]]()
        stack.append(start)

        while !stack.isEmpty {
            let node = stack.removeLast()
            if !visited.contains(node) {
                visited.insert(node)
                nodesInComp[compNumber, default: []].append(node)

                for child in graph[node, default: []] {
                    stack.append(child)
                }
            }
        }
    }

    func buildComponents(_ intervals: [[Int]]) {
        var compNumber = 0

        for interval in intervals {
            if !visited.contains(interval) {
                markComponentDFS(interval, compNumber)
                compNumber += 1
            }
        }
    }

    func merge(_ intervals: [[Int]]) -> [[Int]] {
        buildGraph(intervals)
        buildComponents(intervals)

        var merged = [[Int]]()
        for comp in 0..<nodesInComp.count {
            if let nodes = nodesInComp[comp] {
                merged.append(mergeNodes(nodes))
            }
        }

        return merged
    }
}

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

Please open Telegram to view this post