# CLEAN CODE: MERGE INTERVALS | ARRAY

By: Saurav

2018-02-06 00:45:00 UTC

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Given intervals [1,3],[6,9] insert and merge [2,5] would result in [1,5],[6,9].

Example 2:

Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] would result in [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Make sure the returned intervals are also sorted.

InterviewBit

There are various ways of solving this problem. One approach can be to use hash and store key and value as number line and presence. But that would take O(n**2) time

A really efficient way would be to use stack.

Algo:
1. Sort the intervals
2. Add the first interval in the stack
3. Starting from the second interval, check if the top interval in the stack overlaps with the present interval
If it does, pop the top one, merge the intervals and add to the stack
If it doesn't, add the second one, update top and continue with third value

```p merge_intervals([[1,3],[2,6],[8,10],[15,18]]) == [[1, 6], [8, 10], [15, 18]]
p merge_intervals([[1,3],[2,6],[8,10],[6,6],[15,18]]) == [[1, 6], [8, 10], [15, 18]]
p merge_intervals([[1,3],[6,9],[2,5]]) == [[1,5],[6,9]]

```

lets see the code:

```def merge_intervals(intervals)
return unless intervals
return [] if intervals.length < 1

intervals.sort!{|a,b| a[0] <=> b[0]}

first = intervals[0]
i = 1
stack = Array.new
stack << first

while i < intervals.length
if overlaps(first, intervals[i])
a = stack.pop
first = merge(a, intervals[i])
stack << first
else
first = intervals[i]
stack << first
end
i += 1
end

return stack

end

def merge(a,b)
return [[a[0], b[0]].min, [a[1], b[1]].max]
end

def overlaps(a,b)
(b[1] >= a[0] and b[1] <= a[1]) or (b[0] >= a[0] and b[0] <= a[1]) ? true : false
end
```

All our tests pass as shown below:

Looks good to me.