Merge Intervals

July 14, 2025

Question

You're given a list of intervals, where each interval is a pair [start, end]. Merge all overlapping intervals and return the result.

Two intervals overlap if one starts before the other ends.

Example

Input: [[1, 4], [2, 3]]

Output: [[1, 4]]

Explanation: Since [2, 3] falls completely within [1, 4], we merge them.

My Notes

Sort the intervals by their start times.
Use a stack to keep track of merged intervals.
For each interval:

If it overlaps with the top of the stack, merge it.
If it doesn't, push it as a new interval.

Two intervals [a, b] and [c, d] overlap if b >= c.

package main

import (
    "fmt"
    "sort"
)

type Stack struct {
    items [][]int
}

func (s *Stack) Push(item []int) {
    s.items = append(s.items, item)
}

func (s *Stack) Top() []int {
    return s.items[len(s.items)-1]
}

func (s *Stack) Empty() bool {
    return len(s.items) == 0
}

func merge(intervals [][]int) [][]int {
    stack := Stack{}

    // Sort by Starting Interval in ascending order
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    for _, arr := range intervals {
        if stack.Empty() {
            stack.Push(arr)
        } else {
            // Overlapping case
            if stack.Top()[1] >= arr[0] {
                if stack.Top()[1] <= arr[1] {
                    stack.Top()[1] = arr[1]
                }
            } else {
                stack.Push(arr)
            }
        }
    }

    return stack.items
}

func main() {
    result := merge([][]int{{1, 4}, {2, 3}})
    fmt.Println(result)
}