LeetCode in Ruby: 56. Merge Intervals

Sorting

def merge(intervals)
  merged = []
  intervals.sort_by! { |interval| interval.start }

  intervals.each do |interval|
    if merged.empty? || merged.last.end < interval.start
      merged << interval
    else
      merged.last.end = interval.end if interval.end > merged.last.end
    end
  end

  return merged
end

First of all, we sort the intervals list based on the start value of each interval in the list. Then we iterate through the list and append the current interval to the merged list if:

1. The merged list is empty, or
2. The last interval doesn’t overlap with the current interval, i.e. last.end < interval.start.

Otherwise we should update the end value of the last interval of the merged list. The updated end value should be greater than the previous one.

Time complexity: O(nlgn)

Extra memory: O(1)