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