LeetCode - 56. Merge Intervals

問題

56. Merge Intervals

Ver. 1

1. とりあえず interval を merged_intervals にほりこむ
2. merged_intervals の最後の要素 [a, b] を取り出して、次の interval の [x, y] と重なっているか判定
3. interval が重なってなかったら、[a, b], [x, y] をそのままmerged_intervals にほりこむ
4. 重なってたら、[a, b], [x, y] をマージしてほりこむ

• intervals は事前にソートされていないとうまくいかない
• O(n^2) を避けるため、ソートして、都度マージする

# @param {Integer[][]} intervals
# @return {Integer[][]}
def merge(intervals)
  merged_intervals = []

  intervals.sort.each do |curr|
    last = merged_intervals.pop
    if last.nil?
      merged_intervals << curr
    elsif last[1] < curr[0] || curr[1] < last[0] # Last and curret are not overlapped
      merged_intervals << last << curr
    else # Last and curret are overlapped
      merged_intervals << [(last + curr).min, (last + curr).max]
    end
  end

  merged_intervals
end

スコア

Runtime: 88 ms, faster than 15.18% of Ruby online submissions for Merge Intervals.
Memory Usage: 9.8 MB, less than 100.00% of Ruby online submissions for Merge Intervals.

いまいち...

Ver. 2

コメントいただいて、再度考えてみたバージョン

# @param {Integer[][]} intervals
# @return {Integer[][]}
def merge(intervals)
  merged_intervals = []

  intervals.sort.each do |curr|
    last = merged_intervals.last
    if last.nil?
      merged_intervals << curr
    elsif last[1] < curr[0]  # Last and curret are NOT overlapped
      merged_intervals << curr
    else # Last and curret are overlapped
      last[1] = (last + curr).max
    end
  end

  merged_intervals
end

スコア

Runtime: 60 ms, faster than 44.64% of Ruby online submissions for Merge Intervals.
Memory Usage: 9.7 MB, less than 100.00% of Ruby online submissions for Merge Intervals.

だいぶよくなった