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:
- The
merged
list is empty, or - 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)
Top comments (0)