#14 Array: Merge Overlapping Intervals

tags:Array Medium

Issue

Write a function that takes in a non-empty array of arbitrary intervals, merges any overlapping intervals, and returns the new intervals in no particular order.

Each interval interval is an array of two integers, with interval[0] as the start of the interval and interval[1] as the end of the interval.
Note that back-to-back intervals aren't considered to be overlapping. For example, [1, 5] and [6, 7] aren't overlapping; however, [1, 6] and [6, 7] are indeed overlapping.
Also note that the start of any particular interval will always be less than or equal to the end of that interval.

Sample Input

intervals = [[1, 2], [3, 5], [4, 7], [6, 8], [9, 10]]

Sample Output

[[1, 2], [3, 8], [9, 10]]

// Merge the intervals [3, 5], [4, 7], and [6, 8].
// The intervals could be ordered differently.

Hints

Hint 1

The problem asks you to merge overlapping intervals. How can you determine if two intervals are overlapping?

Hint 2

Sort the intervals with respect to their starting values. This will allow you to merge all overlapping intervals in a single traversal through the sorted intervals.

Hint 3

After sorting the intervals with respect to their starting values, traverse them, and at each iteration, compare the start of the next interval to the end of the current interval to look for an overlap. If you find an overlap, mutate the current interval so as to merge the next interval into it.

Optimal Time & Space Complexity

O(nlog(n)) time | O(n) space - where n is the length of the input array

Solutions

Official

Solution 1

// O(nlog(n)) time | O(n) space - where n is the length of the input array

function mergeOverlappingIntervals(intervals) {
    const sortedIntervals = intervals.sort((a, b) => a[0] - b[0]);
    const mergedIntervals = [];
    let currentInterval = sortedIntervals[0];
    mergedIntervals.push(currentInterval);
    for (const nextInterval of sortedIntervals) {
      const [_, currentIntervalEnd] = currentInterval;
      const [nextIntervalStart, nextIntervalEnd] = nextInterval;
      if (currentIntervalEnd >= nextIntervalStart) currentInterval[1] = Math.max(currentIntervalEnd, nextIntervalEnd);
      else {
        currentInterval = nextInterval;
        mergedIntervals.push(currentInterval);
      }
    }
    return mergedIntervals;
}

Everyone's

東

/// O(nlog(n)) Time | O(n) space - n is the numbers of intervals
function mergeOverlappingIntervals(array) {
  array.sort((a, b) => a[0] - b[0]);
  const result = [array[0]];
  let itvIdx = 0, arrIdx = 1;
  for(const itv of array){
    const [currItvStart, currItvEnd] = result[itvIdx];
    const [nextItvStart, nextItvEnd] = itv;
    if(nextItvStart <= currItvEnd){
      result[itvIdx] = [currItvStart, Math.max(currItvEnd, nextItvEnd)];
    } else {
      result.push(itv);
      itvIdx++;
    }
  }
  return result;
}

Hao

/**
  * Time complexity: O(n) where n stands for array.length
  * Space complexity: O(1)
  */

function mergeOverlappingIntervals(array) {
    array.sort((a, b) => {
        return a[0] === b[0] ? a[1] - b[1] : a[0] - b[0];
    });

    let i = 0;
    let final = array.length - 1;

    while (i < final) {
        const [lStart, lEnd] = array[i];
        const [rStart, rEnd] = array[i + 1];

        if (rStart <= lEnd) {
            array.splice(i, 2, [lStart, rEnd > lEnd ? rEnd : lEnd]);
            final -= 1;
        } else {
            i += 1
        };
    }

    return array;
}

YC

/*
  time: O(n log n) - where n is the length of the given array
  space: O(n) - where n is the length of the given array
*/
function mergeOverlappingIntervals(array) {
  array.sort((a,b)=> a[0] - b[0]);
  let latestInterval = array[0];
  const ans = [latestInterval];
  
  for(const interval of array){
    const [left, right] = interval;
    const [latestLeft, latestRight] = latestInterval;
    if(latestRight < left){
      // latest new
      latestInterval = interval
      ans.push(latestInterval);
    }
    else{
      //covered
      if(latestRight < right){
        //latestRight right
        latestInterval[1] = right;
      }
    }
  }  
  return ans;
}

月薪

Discussion

Concept

1. When should we merge the intervals? When two intervals overlap each other:

const [lStart, lEnd] = intervals[0];
const [rStart, rEnd] = intervals[1];

if (rStart <= lEnd) {
    ...
}

2. If we employ conditional if (rStart <= lEnd) to examine whether to merge two intervals…

• With current array, we need to run two iterations, time complexity as O(n^2), to make sure random two intervals in the array are picked and examined.
• If we sort the array first, we could optimal the time complexity to O(n).

Official solution

Use variable name currentInterval to make the sematics clear instead of array[i]

function mergeOverlappingIntervals(intervals) {
  ...
  mergedIntervals.push(currentInterval);
    
  for (const nextInterval of sortedIntervals) {
    ...
    if (currentIntervalEnd >= nextIntervalStart) currentInterval[1] = Math.max(currentIntervalEnd, nextIntervalEnd);
    else {
      currentInterval = nextInterval;
      mergedIntervals.push(currentInterval);
    }
  }
  ...
}

• Concept of YC's solution is the same as the official one, Hao and Dong use array[i] instead which might be less intuitive.

Hao

Turn space complexity into O(1) with manipulating the original array

• Is this a good practice?