class MergeIntervals

Public Instance Methods

merge(intervals) click to toggle source

Connected Components

# File lib/leetcode_rb/merge_intervals.rb, line 33
def merge(intervals)
  graph = build_graph(intervals)
  nodes_in_comp, comp_num =get_components(graph, intervals)

  (0...comp_num).to_a.map { |comp| merge_nodes(nodes_in_comp[comp])}
end

Private Instance Methods

build_graph(intervals) click to toggle source
# File lib/leetcode_rb/merge_intervals.rb, line 46
def build_graph(intervals)
  graph = Hash.new []

  intervals.each.with_index do |interval, i|
    for j in (i + 1)...intervals.length
      if overlap(interval, intervals[j])
        graph[interval] << intervals[j]
        graph[intervals[j]] << interval
      end
    end
  end

  return graph
end
get_components(graph, intervals) click to toggle source
# File lib/leetcode_rb/merge_intervals.rb, line 67
def get_components(graph, intervals)
  visited = Set.new
  comp_num = 0
  nodes_in_comp = Hash.new []

  make_component_dfs = Proc.new do |start|
    stack = [start]
    while stack
      node = stack.pop()
      unless visited.include?(node)
        visited.add(node)
        nodes_in_comp[comp_num] << node
        stack.concat(graph[node])
      end
    end
  end

  intervals.each do |interval|
    unless visited.include?(interval)
      make_component_dfs.call(interval)
      return nodes_in_comp, comp_num
    end
  end
end
merge_nodes(nodes) click to toggle source
# File lib/leetcode_rb/merge_intervals.rb, line 61
def merge_nodes(nodes)
  min_start = nodes.min_by { |node| node.start }
  max_end = nodes.max_by { |node| node.end }
  Interval.new(min_start, max_end)
end
overlap(node1, node2) click to toggle source
# File lib/leetcode_rb/merge_intervals.rb, line 42
def overlap(node1, node2)
  return node1.start <= node2.end && node2.start <= node1.end
end