Merge Intervals

main.md

Approach

1. Pointers are assigned to track the start and end values of the interval groups.
2. if there is not more than 1 interval group i return the interval array.
3. The values in the interval groups are sorted based on the their size so i can check accurately if adjacent values of the interval groups overlap.
4. A loop is created to check if the interval values overlap.if they do ,they are merged and added to the array to be returned. then i move forward and check if the new merged interval overlaps again, if it doesnt i add it to the array to be returned like that.

Complexity

• Time complexity:O(Nlogn)

• Space complexity: O(N)

Code

function merge(intervals: number[][]): number[][] {
    let start = 0;
    let end = 1;
    let overlaps: number[][] = [];
    let i = 0;

    if (intervals.length <= 1) return intervals;

    let sortedInt = intervals.sort((a, b) => a[start] - b[start]);

    while (i < sortedInt.length) {
        let curr = sortedInt[i];
        while (
            i + 1 < sortedInt.length &&
            curr[end] >= sortedInt[i + 1][start]
        ) {
            curr[end] = Math.max(curr[end], sortedInt[i + 1][end]);
            i++;
        }

        overlaps.push(curr);
        i++;
    }

    return overlaps;
}