[Leetcode] Merge Intervals

56. Merge Intervals

Given an array of intervalswhere intervals[i] = [start``i``, end``i``], 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 <= 10``4

intervals[i].length == 2

0 <= start``i`` <= end``i`` <= 10``4

how to approach?

function merge(intervals: number[][]): number[][] {
    intervals.sort((a,b)=>a[0]-b[0])
    
    let merged:number[][]= []
    
    for(let item of intervals){

        if(merged.length===0 || merged[merged.length-1][1] < item[0]){
            merged.push(item)
        } else {
            const max = Math.max(merged[merged.length-1][1],item[1])
            merged[merged.length-1][1] = max
        }
    }
    
    return merged
}

1. sort the intervals input based on the first element in each element. smallest comes first and biggest at the last.
2. create merged array to put the intervals array in it.
3. in for loop of intervals, when merged array doesn't have anything or the last element in merged arrays' second element is smaller than the current intervals item's first element, push the item into merged arrray.
4. other than those cases, compare the second item in last element of merged array and the current interval element's second item to select the bigger one to set it as the merged array's last element's second item.
5. lastly return the merged array.

summary

this leetcode problem is solved by typescript language.

To compare the items value in the intervals, first sort it out secondly compare the last item to intervals' current element's values. So decide which one is bigger so put it as last item so there is no overlapping between the intervals.