Сложность: 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 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)]
Ставь 👍 и забирай 📚 Базу знаний