You will be given a set of intervals in form of 2-D array, write a program to merge all the overlapping intervals and return the array.

Problem Note:

  • You will be given a 2-dimensional array consisting of n rows and 2 columns.
  • Each row has a interval starting from value at first column and ending at value at second column.
  • Two intervals t1 and t2 are said to be overlapping if and only if t1.start < t2.start < t1.end
  • Even if t1 entirely engulfs t2 completely, its said to be overlapping.

Example 1

Input: [[1,5], [2,3], [4,8], [9,10]]
Output: [[1,8], [9,10]]

Example 2

Input: [[1,4], [5,8], [8,10], [12,15]]
Output: [[1,4], [5,10], [12,15]]

Example 3

Input: [[3,8], [4,6], [6,10]]
Output: [[3,10]]