Intervals

This technique is very useful when dealing with intervals, overlapping items or merging intervals.

How to Identify

• Data Structure Involves: Array
• Question Type: When asked to deal with problems involving intervals, overlapping items or merging intervals.

Example

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

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

Typescript

function merge(intervals: number[][]): number[][] {
    const inputLength = intervals.length
    if(inputLength === 0) return []
    
    intervals.sort((a, b) => a[0] - b[0])
    const result: number[][] = [intervals[0]]

    for(let [start, end] of intervals){
        const lastEnd = result.slice(-1)[0][1]

        if(start <= lastEnd) {
            result.slice(-1)[0][1] = Math.max(lastEnd, end)
        } else {
            result.push([start, end])
        }
    }
    
    return result
}

Related Problems

	Problems	Difficulty
1	Meeting Rooms (Leetcode Premium)	Easy
2	Merge Intervals	Medium
3	Non-overlapping Intervals	Medium
4	Meeting Rooms II (Leetcode Premium)	Medium
5	Insert Interval	Hard