The Problem

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]

Output: [[1,5]]

Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Solution

Given

An array of arrays is given. Each array nested with the outer array contains two number values. The second value will always be greater than the first value. This pair of values represents an interval. Throughout this article, the term ‘array’ will refer to the outer array and ‘interval’ will refer to an inner array. This given array is unsorted.

Return

An array with the same structure as the given array. The difference is that this array should have no nested arrays with intervals that overlap. In other words, our job is to combine the overlapping intervals in the given array before returning it.

Problem Solving Strategy

The problem can be broken down into three parts:

• How to navigate the array:
  • This will be the main difference between the brute force approach and the more efficient approach and it will be covered in detail in those sections.
• How to identify when there is an overlap:
  • When navigating the array, you are continuously finding two intervals and comparing them to each other.
  • How exactly will you know when the two intervals in front of you overlap?
  • Study some examples of two intervals and see what exactly about them tells you you that they do or do not overlap.

// no overlap
[1, 4], [5, 6]
[3, 6], [1, 2]

// overlap
[1, 3], [3, 5]
[2, 3], [1, 6]
[5, 7], [4, 6]

• What facts are always true about the pairs of intervals that overlap that are never true about the pairs that don't?
• There are two conditions that need to be met in order for there to be an overlap.
• The first value in the first interval needs to be less than or equal to the second value in the second interval. Also, the second value in the first interval needs to be greater than the first value in the second interval.
• In other words, they overlap if :

array[i][1] >= array[i + 1][0] && array[i][0] <= array[i + 1][1]
// i and j represent the indices of two different intervals of the array

• What to do when an overlap is identified:
  • Once overlapping intervals are found, it is finally time to take action.
  • How do you combine two intervals and create a new interval that fully encompasses both of them?
  • All that needs to be done to figure this out is find the highest and lowest values in either interval.
  • We already know that the first value in every interval is lower than the second.
  • Therefore, we simply take the minimum between the two intervals first value and the maximum between the two intervals second value
  • The max and min are then combined to form the new interval
  • In other words, new interval can be calculated with:

[Math.min(array[i][0], array[j][0]), Math.max(array[i][1], array[j][1])]
// i and j represent the indices of two different intervals of the array

• Once the new interval is calculated, the array needs to be updated.
• This means the two intervals that were combined need to be removed and the new interval needs to be added in.
• This process will be done slightly differently depending on the approach used.

Approach One (Brute Force)

This approach will run in O(N^2) time. It will iterate through the array. At each iteration, it will iterate through the array again and compare the current interval to every other interval in the array. If it makes it through the entire array finding no overlapping interval, you will know that this specific interval cannot be combined with anything else and should be left alone. If an overlapping interval is found, the two overlapping intervals are both removed from the array and the new combined array is added in at your current index. The iteration being done at your current index is then started back from the beginning since you have a new value at your current index. This approach will get the correct answer. However, the problem can be solved in better than O(N^2) time complexity.

The Code

function mergeIntervals(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length; j++) {
      if (i === j) continue
      if (array[i][1] >= array[j][0] && array[i][0] <= array[j][1]) {
        let k = [Math.min(array[i][0], array[j][0]), Math.max(array[i][1], array[j][1])]
        array.splice(i, 1, k)
        array.splice(j, 1)
        if (i > 0) i--
      }
    }
  }
  return array
}

Approach Two (Sort First)

As stated in the Problem Solving Strategy section, this approach has the same core algorithm as the brute force method. The difference is that this time, the array is sorted before starting the loop and there is no nested loop. One way to help identify when a sorting solution is an option is simply to be aware and recognize when sorting is beneficial. Know that sorting takes O(NlogN) time. So, if your solution is already at O(NlogN) time or worse, there is not need to worry about its effect on time complexity. But does it provide value to this specific problem? Yes. In this case, sorting allows you identify and combine all overlapping intervals in a single pass. The benefit of sorting here is that you no longer have to check every single combination. Once the array is sorted, you can simply compare the intervals that are next to each other. Since the array is sorted, you now know that any overlaps that occur will be happening with two intervals that sit within one index of each other. So, you can make one pass through the array, comparing the interval at your current index to the interval at the following index. Here is a visual showcasing how sorting simplifies the problem:

// example input array
[[2, 3], [5, 7], [1, 4], [8, 9], [3, 4]]

// visual representation before sorting
1   2   3   4   5   6   7   8   9
|   XXXXX   |   |   |   |   |   | [2, 3]
|   |   |   |   XXXXXXXXX   |   | [5, 7]
XXXXXXXXXXXXX   |   |   |   |   | [1, 4]
|   |   |   |   |   |   |   XXXXX [8, 9]
|   |   XXXXX   |   |   |   |   | [3, 4]

// visual representation after sorting
1   2   3   4   5   6   7   8   9
XXXXXXXXXXXXX   |   |   |   |   | [1, 4]
|   XXXXX   |   |   |   |   |   | [2, 3]
|   |   XXXXX   |   |   |   |   | [3, 4]
|   |   |   |   XXXXXXXXX   |   | [5, 7]
|   |   |   |   |   |   |   XXXXX [8, 9]

Note that after sorting the array, all overlapping intervals that exist will now always sit next to each other.

The Code

function mergeIntervals2(array) {
  array.sort((a, b) => {
    if (a[0] === b[0]) {
      return a[1] - b[1]
    }
    return a[0] - b[0]
  })
  for (let i = 0; i < array.length; i++) {
    if (i === array.length - 1) continue
    if (array[i][1] >= array[i + 1][0] && array[i][0] <= array[i + 1][1]) {
      array.splice(i, 2, [Math.min(array[i][0], array[i + 1][0]), Math.max(array[i][1], array[i + 1][1])])
      i--
    }
  }
  return array
}