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

Problem Note:

  • You will be given a 2-D array intervals consisting of r rows and 2 columns.
  • Each row has an interval starting from the value at the first column and ending at a value in the 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, it's said to be overlapping.

Example 1

Input: [[1, 5], [2, 3], [4, 8], [9, 10]]
Output: [[1, 8], [9, 10]]
Explanation: In the above example, [[1, 5], [2, 3], [4, 8]] will be merged in the interval [1, 8], while [9, 10] is a separte interval. Thus we get [[1, 8], [9, 10]] as output. 

Example 2

Input: [[1, 4], [5, 8], [8, 10], [12, 15]]
Output: [[1, 4], [5, 10], [12, 15]]
Explanation: In the above example, [1, 4] is a separte interval, [[5, 8], [8, 10]] will be merged in the interval [5, 10], and [12, 15] is a separate interval. Thus we get [[1, 4], [5, 10], [12, 15]] as output.

Example 3

Input: [[3, 8], [4, 6], [6, 10]]
Output: [[3, 10]]
Explanation: In the above example, [[3, 8], [4, 6], [6, 10]] will be merged in a single interval [3, 10]. Thus we get [[3, 10]] as output.