matoski.com

Given an array (list) of intervals as input where each interval has a start and end timestamps. Input array is sorted by starting timestamps. You are required to merge overlapping intervals and return output array (list).

Consider below input array. Intervals (2, 10), (4, 12), (11, 13), (15, 20) are overlapping so should be merged to one big interval (2, 13). Similarly interval (15, 20) doesn’t overlap anywhere so it should be added to the merged overlapping interval list.

The problem can be solved with a simple linear scan. And the intervals are sorted by the starting timestamps.

We can also expand this solution for an unsorted array of intervals, by just sorting the intervals based on the start time.

Algorithm

• List of input intervals is given, and we we keep the merged inteval list in a separate list
• For each interval in the list
  • If interval is overlapping with the last interval in the output list we merge these two intervals and update the last interval of the output interval with the merged one
  • Otherwise we add the input interval to the output interval

Solution

let merge_intervals = function(v1) {
  if (!v1 || v1.length === 0) {
    return;
  }

  let v2 = [];
  v2.push([ v1[0][0], v1[0][1] ]);

  for (let i = 0; i < v1.length; i++) {
    let x1 = v1[i][0];
    let y1 = v1[i][1];
    let x2 = v2[v2.length - 1][0];
    let y2 = v2[v2.length - 1][1];

    if (y2 >= x1) {
      v2[v2.length - 1][1] = Math.max(y1, y2);
    } else {
      v2.push([ x1, y1 ]);
    }

  }
  return v2;
};

console.log(merge_intervals([[1,5],[3,7],[4,6],[6,8],[10,12],[11,15]]));
console.log(merge_intervals([[4,12],[13,16],[19,20],[20,24]]));
console.log(merge_intervals([[2,10],[4, 12], [11, 13], [15, 20]]));

And the output would be

[ [ 1, 8 ], [ 10, 15 ] ]
[ [ 4, 12 ], [ 13, 16 ], [ 19, 24 ] ]
[ [ 2, 12 ] ]

Runtime complexity: Linear O(n), if we need to sort the array before we start then the complexity is O(nlogn)

Memory complexity: O(n) worst case, when they are no overlapping intervals