# #14 Array: Merge Overlapping Intervals

###### tags:`Array` `Medium`

<br>

## 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

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

<br />

:::spoiler 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.
:::

<br />

:::spoiler 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
:::spoiler
O(nlog(n)) time | O(n) space - where n is the length of the input array
:::

## Solutions

### Official

:::spoiler Solution 1
<br />

// 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;
}

:::

<br />

### Everyone's

:::spoiler 東

/// 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;
}

:::

<br>

:::spoiler 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;
}

:::

<br>

:::spoiler 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;
}

:::

<br>

:::spoiler 月薪

:::

<br>

## 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?