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.


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.

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

Let's start with writing tests first.

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 =
  stack << first
  while i < intervals.length
    if overlaps(first, intervals[i])
      a = stack.pop
      first = merge(a, intervals[i])
      stack << first
      first = intervals[i]
      stack << first
     i += 1 
 return stack

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

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

All our tests pass as shown below:


Looks good to me.

Let me know what you think!
twitter: sprakash24oct

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)