56. Merge Intervals

 Merge Intervals

Problem Description

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] overlap, 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.

 

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

Approach) Native

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    intervals = intervals.sort((a, b) => a[0] - b[0]);
    
    for (let i = 0; i < intervals.length - 1; i++)  {
        if (intervals[i][1] >= intervals[i+1][0])   {
            intervals[i][1] = Math.max(intervals[i][1],intervals[i+1][1])
            intervals.splice(i+1,1);
            i--;
        }
    }
    
    return intervals;
};

Approach) Another 

var merge = function(intervals) {
    // check edge case
    if(intervals.length <= 1) return intervals;
    
    // first SORT your intervals by first element, in ascending order
    // O(nlogn) time complexity
    intervals.sort((a,b) => a[0]-b[0]);
    let ans = [];
    
    // push first interval to ans
    ans.push(intervals[0]);
    lastInterval = ans[0];
    
    // loop through rest of intervals. If they overlap, then change 2nd index of the last interval in ans to the max of currentInterval[1] and lastInterval[1]
    // This covers the case where your 2 intervals are for ex. [1,5] [2,4]
    // If they don't overlap, push currentInterval into array and update lastInterval
    for(let i = 1; i < intervals.length; i++) {
        let lastIntervalEnd = lastInterval[1];
        let currentIntervalStart = intervals[i][0];
        let currentIntervalEnd = intervals[i][1];
        
        if(currentIntervalStart <= lastIntervalEnd) {
            lastInterval[1] = Math.max(currentIntervalEnd, lastIntervalEnd);
        } else {
            ans.push(intervals[i]);
            lastInterval = ans[ans.length-1];
        }
    }
    
    return ans;

};

Approach) Recursion

var merge = function(intervals) {
  if (intervals.length === 0) return [];

  intervals.sort(function(a, b) {
    return a[0] - b[0];
  });

  var result = [intervals[0]];
  helper(intervals, 1, 0, result);
  return result;
};

function helper(arr, i, j, result) {
  if (i >= arr.length) {
    return;
  }
  var afterStart = arr[i][0];
  var afterEnd = arr[i][1];

  var beforeStart = result[j][0];
  var beforeEnd = result[j][1];

  if (afterStart <= beforeEnd) {
    result[j][0] = Math.min(beforeStart, afterStart);
    result[j][1] = Math.max(beforeEnd, afterEnd);
  } else {
    result.push(arr[i]);
  }
  helper(arr, i + 1, result.length - 1, result);
}

Approach) Reduce 

var merge = function (intervals) {
    intervals.sort(([a], [b]) => a - b)

    return intervals
        .reduce((acc, [c, d]) => {
            const [a, b] = acc.pop()
            return b >= c ? [...acc, [a, Math.max(b, d)]] : [...acc, [a, b], [c, d]]
        }, [intervals.shift()])
        .filter(Boolean)

};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 56. Merge Intervals

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!