Merge Intervals using Javascript

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.

Approach:

A simple approach is to sort the intervals by their starting points,Then, we take the first interval and compare its end with the next intervals starts. As long as they overlap, we update the end to be the max end of the overlapping intervals. Once we find a non overlapping interval, we can add the previous extended interval and start again.

Algorithm:

1. Sort the intervals based on their starting point.
Push the first interval on to a stack.
3. For each interval
   a. If the current interval does not overlap with the stack 
       top, push it.
   b. If the current interval overlaps with stack top and ending
       time of current interval is more than that of stack top, 
       update stack top with the ending  time of current interval.
4. At the end stack contains the merged intervals.

Time Complexity Analysis

Time Complexity: O(nlgn)

Space Complexity: O(1) (or O(n))

Solution using Javascript:

const merge = function(intervals) {
    const stack = [];
    let start = 0;
    let end = 1;
    let index = 0;
    if(intervals.length < 1) {
        return [];
    }
    intervals.sort((a, b) => a[0] - b[0]);
    stack.push(intervals[0]);
    for(let i  = 1; i < intervals.length; i += 1 ) {
        const top = stack.pop();
        if(top[end] < intervals[i][start]) {
            stack.push(top);
            stack.push(intervals[i]);
        } else {
            top[end] = Math.max(intervals[i][end], top[end]);
            stack.push(top);
        }
    }
    return stack;
    
};