Merge Intervals

1. Problem Description

Given an array intervals representing a collection of intervals, where a single interval is intervals[i] = [starti, endi], merge all overlapping intervals and return an array of non-overlapping intervals that exactly covers all intervals in the input.

2. Approach

1. Approach 1
   • First sort by the first element so the intervals are in ascending order
   • Traverse each interval. If it overlaps with the previous interval, take their union; otherwise append it directly

3. Implementation

3.1. Stack

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        a := intervals[i]
        b := intervals[j]
        return a[0] < b[0]
    })

    stack := make([][]int, 0)
    for _, interval := range intervals {
        if len(stack) == 0 {
            stack = append(stack, interval)
        }else {
            top := stack[len(stack)-1]
            // No overlap between intervals
            if top[1] < interval[0] {
                stack = append(stack, interval)
            // Intervals overlap
            }else {
                top[1] = max(top[1], interval[1])
                top[0] = min(top[0],interval[0])
               
            }
        }
    }

    return stack
}

func max(a, b int) int {
    if a > b {
        return a
    }

    return b
}

func min(a, b int) int {
    if a > b {
        return b
    }

    return a
}

4. References

• 56. Merge Intervals - LeetCode