Merge an Array With Overlapping Intervals
Understand how to merge overlapping intervals in a sorted array using a linear scan approach. This lesson helps you develop efficient problem-solving skills with arrays by updating and appending intervals to create a merged output. You will also learn the time and space complexities associated with this approach.
We'll cover the following...
Statement
We’re given an array of interval pairs as input where each interval has a start and end timestamp. The input array is sorted by starting timestamps. Merge the overlapping intervals and return a new output array.
Example
Consider the input array below. Intervals [1, 5], [3, 7], [4, 6], [6, 8] are overlapping, so they should be merged to one big interval [1, 8]. Similarly, intervals [10, 12] and [12, 15] are also overlapping and should be merged to [10, 15].
Sample input
intervals = [[1,3],[2,6],[8,10],[15,18]]