56. Merge Intervals

import java.util.*;
class Solution {
    private Map<int[], List<int[]>> graph;
    private Map<Integer, List<int[]>> nodesInComp;
    private Set<int[]> visited;
    private boolean overlap(int[] a, int[] b) {
        return a[0] <= b[1] && b[0] <= a[1];
    }
    private void buildGraph(int[][] intervals) {
        graph = new HashMap<>();
        for (int[] interval : intervals) {
            graph.put(interval, new LinkedList<>());
        }
        for (int[] interval1 : intervals) {
            for (int[] interval2 : intervals) {
                if (overlap(interval1, interval2)) {
                    graph.get(interval1).add(interval2);
                    graph.get(interval2).add(interval1);
                }
            }
        }
    }
    private int[] mergeNodes(List<int[]> nodes) {
        int minStart = nodes.get(0)[0];
        for (int[] node : nodes) {
            minStart = Math.min(minStart, node[0]);
        }
        int maxEnd = nodes.get(0)[1];
        for (int[] node : nodes) {
            maxEnd = Math.max(maxEnd, node[1]);
        }
        return new int[] { minStart, maxEnd };
    }
    private void markComponentDFS(int[] start, int compNumber) {
        Stack<int[]> stack = new Stack<>();
        stack.add(start);
        while (!stack.isEmpty()) {
            int[] node = stack.pop();
            if (!visited.contains(node)) {
                visited.add(node);
                if (nodesInComp.get(compNumber) == null) {
                    nodesInComp.put(compNumber, new LinkedList<>());
                }
                nodesInComp.get(compNumber).add(node);
                for (int[] child : graph.get(node)) {
                    stack.add(child);
                }
            }
        }
    }
    private void buildComponents(int[][] intervals) {
        nodesInComp = new HashMap<>();
        visited = new HashSet<>();
        int compNumber = 0;
        for (int[] interval : intervals) {
            if (!visited.contains(interval)) {
                markComponentDFS(interval, compNumber);
                compNumber++;
            }
        }
    }
    public int[][] merge(int[][] intervals) {
        buildGraph(intervals);
        buildComponents(intervals);
        List<int[]> merged = new LinkedList<>();
        for (int comp = 0; comp < nodesInComp.size(); comp++) {
            merged.add(mergeNodes(nodesInComp.get(comp)));
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
import java.util.*;
class Solution {
    private Map<int[], List<int[]>> graph;
    private Map<Integer, List<int[]>> nodesInComp;
    private Set<int[]> visited;
    private boolean overlap(vector<int>& a, vector<int>& b) {
        return a[0] <= b[1] && b[0] <= a[1];
    }
    private void buildGraph(int[][] intervals) {
        graph = new HashMap<>();
        for (vector<int>& interval : intervals) {
            graph.put(interval, new LinkedList<>());
        }
        for (vector<int>& interval1 : intervals) {
            for (vector<int>& interval2 : intervals) {
                if (overlap(interval1, interval2)) {
                    graph.get(interval1).add(interval2);
                    graph.get(interval2).add(interval1);
                }
            }
        }
    }
    private vector<int>& mergeNodes(List<int[]> nodes) {
        int minStart = nodes.get(0)[0];
        for (vector<int>& node : nodes) {
            minStart = Math.min(minStart, node[0]);
        }
        int maxEnd = nodes.get(0)[1];
        for (vector<int>& node : nodes) {
            maxEnd = Math.max(maxEnd, node[1]);
        }
        return new int[] { minStart, maxEnd };
    }
    private void markComponentDFS(vector<int>& start, int compNumber) {
        stack<int[]> stack = new Stack<>();
        stack.add(start);
        while (!stack.isEmpty()) {
            vector<int>& node = stack.pop();
            if (!visited.contains(node)) {
                visited.add(node);
                if (nodesInComp.get(compNumber) == null) {
                    nodesInComp.put(compNumber, new LinkedList<>());
                }
                nodesInComp.get(compNumber).add(node);
                for (vector<int>& child : graph.get(node)) {
                    stack.add(child);
                }
            }
        }
    }
    private void buildComponents(int[][] intervals) {
        nodesInComp = new HashMap<>();
        visited = new HashSet<>();
        int compNumber = 0;
        for (vector<int>& interval : intervals) {
            if (!visited.contains(interval)) {
                markComponentDFS(interval, compNumber);
                compNumber++;
            }
        }
    }
    public int[][] merge(int[][] intervals) {
        buildGraph(intervals);
        buildComponents(intervals);
        List<int[]> merged = new LinkedList<>();
        for (int comp = 0; comp < nodesInComp.size(); comp++) {
            merged.add(mergeNodes(nodesInComp.get(comp)));
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

import java.util.*;

class Solution {
    private Map<int[], List<int[]>> graph;
    private Map<Integer, List<int[]>> nodesInComp;
    private Set<int[]> visited;

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

    private void buildGraph(int[][] intervals) {
        graph = new HashMap<>();
        for (int[] interval : intervals) {
            graph.put(interval, new LinkedList<>());
        }

        for (int[] interval1 : intervals) {
            for (int[] interval2 : intervals) {
                if (overlap(interval1, interval2)) {
                    graph.get(interval1).add(interval2);
                    graph.get(interval2).add(interval1);
                }
            }
        }
    }

    private int[] mergeNodes(List<int[]> nodes) {
        int minStart = nodes.get(0)[0];
        for (int[] node : nodes) {
            minStart = Math.min(minStart, node[0]);
        }

        int maxEnd = nodes.get(0)[1];
        for (int[] node : nodes) {
            maxEnd = Math.max(maxEnd, node[1]);
        }

        return new int[] { minStart, maxEnd };
    }

    private void markComponentDFS(int[] start, int compNumber) {
        Stack<int[]> stack = new Stack<>();
        stack.add(start);

        while (!stack.isEmpty()) {
            int[] node = stack.pop();
            if (!visited.contains(node)) {
                visited.add(node);

                if (nodesInComp.get(compNumber) == null) {
                    nodesInComp.put(compNumber, new LinkedList<>());
                }
                nodesInComp.get(compNumber).add(node);

                for (int[] child : graph.get(node)) {
                    stack.add(child);
                }
            }
        }
    }

    private void buildComponents(int[][] intervals) {
        nodesInComp = new HashMap<>();
        visited = new HashSet<>();
        int compNumber = 0;

        for (int[] interval : intervals) {
            if (!visited.contains(interval)) {
                markComponentDFS(interval, compNumber);
                compNumber++;
            }
        }
    }

    public int[][] merge(int[][] intervals) {
        buildGraph(intervals);
        buildComponents(intervals);

        List<int[]> merged = new LinkedList<>();
        for (int comp = 0; comp < nodesInComp.size(); comp++) {
            merged.add(mergeNodes(nodesInComp.get(comp)));
        }

        return merged.toArray(new int[merged.size()][]);
    }
}

var overlap = function (a, b) {
    return a[0] <= b[1] && b[0] <= a[1];
};
var buildGraph = function (intervals) {
    var graph = new Map();
    for (var i = 0; i < intervals.length; i++) {
        for (var j = i + 1; j < intervals.length; j++) {
            if (overlap(intervals[i], intervals[j])) {
                if (graph.has(intervals[i])) {
                    graph.get(intervals[i]).push(intervals[j]);
                } else {
                    graph.set(intervals[i], [intervals[j]]);
                }
                if (graph.has(intervals[j])) {
                    graph.get(intervals[j]).push(intervals[i]);
                } else {
                    graph.set(intervals[j], [intervals[i]]);
                }
            }
        }
    }
    return graph;
};
var mergeNodes = function (nodes) {
    var minStart = Infinity;
    var maxEnd = -Infinity;
    for (var node of nodes) {
        minStart = Math.min(minStart, node[0]);
        maxEnd = Math.max(maxEnd, node[1]);
    }
    return [minStart, maxEnd];
};
var markComponentDFS = function (
    start,
    graph,
    nodesInComp,
    compNumber,
    visited,
) {
    var stack = [start];
    while (stack.length) {
        var node = stack.pop();
        if (!visited.has(node)) {
            visited.add(node);
            if (nodesInComp[compNumber]) {
                nodesInComp[compNumber].push(node);
            } else {
                nodesInComp[compNumber] = [node];
            }
            if (graph.has(node)) {
                for (var child of graph.get(node)) {
                    stack.push(child);
                }
            }
        }
    }
};
var merge = function (intervals) {
    var graph = buildGraph(intervals);
    var nodesInComp = {};
    var visited = new Set();
    var compNumber = 0;
    for (var interval of intervals) {
        if (!visited.has(interval)) {
            markComponentDFS(interval, graph, nodesInComp, compNumber, visited);
            compNumber++;
        }
    }
    var merged = [];
    for (var comp = 0; comp < compNumber; comp++) {
        merged.push(mergeNodes(nodesInComp[comp]));
    }
    return merged;
};

import collections

class Solution:
    def overlap(self, a, b):
        return a[0] <= b[1] and b[0] <= a[1]

    def buildGraph(self, intervals):
        graph = collections.defaultdict(list)
        for i, interval_i in enumerate(intervals):
            for j in range(i + 1, len(intervals)):
                if self.overlap(interval_i, intervals[j]):
                    graph[tuple(interval_i)].append(intervals[j])
                    graph[tuple(intervals[j])].append(interval_i)
        return graph

    def mergeNodes(self, nodes):
        min_start = min(node[0] for node in nodes)
        max_end = max(node[1] for node in nodes)
        return [min_start, max_end]

    def getComponents(self, graph, intervals):
        visited = set()
        comp_number = 0
        nodes_in_comp = collections.defaultdict(list)

        def markComponentDFS(start):
            stack = [start]
            while stack:
                node = tuple(stack.pop())
                if node not in visited:
                    visited.add(node)
                    nodes_in_comp[comp_number].append(node)
                    stack.extend(graph[node])

        for interval in intervals:
            if tuple(interval) not in visited:
                markComponentDFS(interval)
                comp_number += 1

        return nodes_in_comp, comp_number

    def merge(self, intervals):
        graph = self.buildGraph(intervals)
        nodes_in_comp, number_of_comps = self.getComponents(graph, intervals)
        return [self.mergeNodes(nodes_in_comp[comp]) for comp in range(number_of_comps)]

func overlap(a []int, b []int) bool {
    return a[0] <= b[1] && b[0] <= a[1]
}

func buildGraph(intervals [][]int) map[int][]int {
    graph := make(map[int][]int)
    for i, interval1 := range intervals {
        for j := i + 1; j < len(intervals); j++ {
            interval2 := intervals[j]
            if overlap(interval1, interval2) {
                graph[i] = append(graph[i], j)
                graph[j] = append(graph[j], i)
            }
        }
    }
    return graph
}

func mergeNodes(nodes []int, intervals [][]int) []int {
    minStart := intervals[nodes[0]][0]
    maxEnd := intervals[nodes[0]][1]
    for _, i := range nodes {
        minStart = int(math.Min(float64(minStart), float64(intervals[i][0])))
        maxEnd = int(math.Max(float64(maxEnd), float64(intervals[i][1])))
    }
    return []int{minStart, maxEnd}
}

func markComponentDFS(
    i int,
    compNumber int,
    visited map[int]bool,
    graph map[int][]int,
    nodesInComp map[int][]int,
) {
    stack := []int{i}
    for len(stack) != 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if _, ok := visited[node]; !ok {
            visited[node] = true
            nodesInComp[compNumber] = append(nodesInComp[compNumber], node)
            for _, child := range graph[node] {
                stack = append(stack, child)
            }
        }
    }
}

func merge(intervals [][]int) [][]int {
    graph := buildGraph(intervals)
    nodesInComp := make(map[int][]int)
    visited := make(map[int]bool)
    compNumber := 0
    for i := range intervals {
        if _, ok := visited[i]; !ok {
            markComponentDFS(i, compNumber, visited, graph, nodesInComp)
            compNumber++
        }
    }
    merged := make([][]int, 0)
    for comp := 0; comp < compNumber; comp++ {
        merged = append(merged, mergeNodes(nodesInComp[comp], intervals))
    }
    return merged
}

Explanation

Algorithm

1️⃣

Представление графа:

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

2️⃣

Определение компонент связности:

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

3️⃣

Объединение интервалов внутри компонент:

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