Leetcode problem 130 - Merge Intervals

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

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  let result = [intervals[0]];
  for (let inter of intervals) {
    let end1 = result[result.length - 1][1];
    let start = inter[0];
    let end2 = inter[1];

    if (end1 >= start) {
      result[result.length - 1][1] = Math.max(end1, end2);
    } else {
      result.push(inter);
    }
  }
  return result;
};

This algorithm has a time complexity of O(n log n) due to the sorting step, where n is the number of intervals. The merging step runs in linear time, making the overall time complexity O(n log n).

The space complexity is O(n), where n is the number of intervals in the input array.