Merge Overlapping Intervals in DSA Go

Mental Model

We combine intervals that touch or overlap into one bigger interval so no two intervals cover the same range twice.

Analogy: Imagine you have several booked time slots on a calendar. If some bookings overlap or touch, you merge them into one longer booking to avoid confusion.

Intervals before merge:
[1,3] -> [2,6] -> [8,10] -> [15,18]

Intervals after merge:
[1,6] -> [8,10] -> [15,18]

Dry Run Walkthrough

Input: intervals: [[1,3], [2,6], [8,10], [15,18]]

Goal: Merge all overlapping intervals into combined intervals without overlaps

Step 1: Sort intervals by start time

[1,3] -> [2,6] -> [8,10] -> [15,18]

Why: Sorting helps us check intervals in order to merge overlaps easily

Step 2: Start with first interval [1,3] in merged list

merged: [1,3]

Why: We need a base interval to compare others against

Step 3: Check next interval [2,6], it overlaps with [1,3], merge to [1,6]

merged: [1,6]

Why: Because 2 ≤ 3, intervals overlap, so we combine to cover full range

Step 4: Check next interval [8,10], no overlap with [1,6], add as new interval

merged: [1,6] -> [8,10]

Why: 8 > 6 means no overlap, so keep separate

Step 5: Check last interval [15,18], no overlap with [8,10], add as new interval

merged: [1,6] -> [8,10] -> [15,18]

Why: 15 > 10 means no overlap, so keep separate

Result:

Final merged intervals:
[1,6] -> [8,10] -> [15,18]

Annotated Code

DSA Go

package main

import (
	"fmt"
	"sort"
)

type Interval struct {
	start int
	end   int
}

func mergeIntervals(intervals []Interval) []Interval {
	if len(intervals) == 0 {
		return intervals
	}

	// Sort intervals by start time
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i].start < intervals[j].start
	})

	merged := []Interval{intervals[0]} // start with first interval

	for i := 1; i < len(intervals); i++ {
		last := &merged[len(merged)-1]
		if intervals[i].start <= last.end {
			// Overlap detected, merge intervals
			if intervals[i].end > last.end {
				last.end = intervals[i].end
			}
		} else {
			// No overlap, add new interval
			merged = append(merged, intervals[i])
		}
	}

	return merged
}

func main() {
	intervals := []Interval{{1, 3}, {2, 6}, {8, 10}, {15, 18}}
	merged := mergeIntervals(intervals)
	for _, iv := range merged {
		fmt.Printf("[%d,%d] ", iv.start, iv.end)
	}
	fmt.Println()
}

sort.Slice(intervals, func(i, j int) bool { return intervals[i].start < intervals[j].start })

Sort intervals by their start time to process in order

merged := []Interval{intervals[0]}

Initialize merged list with first interval as base

for i := 1; i < len(intervals); i++ {

Iterate over remaining intervals to check for overlaps

if intervals[i].start <= last.end {

Check if current interval overlaps with last merged interval

if intervals[i].end > last.end { last.end = intervals[i].end }

Extend the last merged interval end if current interval goes further

else { merged = append(merged, intervals[i]) }

No overlap, add current interval as new merged interval

Output

[1,6] [8,10] [15,18] 

Complexity Analysis

Time: O(n log n) because sorting the intervals takes O(n log n) and merging takes O(n)

Space: O(n) because in worst case no intervals overlap and merged list stores all intervals

vs Alternative: Naive approach checking every pair for overlap is O(n^2), so sorting + one pass merge is more efficient

Edge Cases

empty intervals list

returns empty list immediately

DSA Go

if len(intervals) == 0 { return intervals }

all intervals non-overlapping

merged list is same as input intervals

DSA Go

else { merged = append(merged, intervals[i]) }

all intervals overlapping into one big interval

merged list contains single interval covering all

DSA Go

if intervals[i].start <= last.end { if intervals[i].end > last.end { last.end = intervals[i].end } }

When to Use This Pattern

When you see a list of ranges or time slots and need to combine overlapping or touching ones, use the merge intervals pattern to simplify and reduce them.

Common Mistakes

Mistake: Not sorting intervals before merging, causing incorrect merges
Fix: Always sort intervals by start time before merging

Mistake: Not updating the end of merged interval when current interval extends beyond it
Fix: Check and update the end of last merged interval if current interval's end is larger

Summary

Merges overlapping intervals into combined intervals without overlaps.

Use when you need to simplify overlapping ranges or time slots into non-overlapping ones.

Sort intervals first, then merge by extending or adding intervals as you go.

Practice

1. What is the main goal when merging overlapping intervals in a list like [[1,3],[2,6],[8,10]]?

easy

A. Remove all intervals that overlap

B. Sort intervals by their end values only

C. Combine intervals that overlap into one continuous interval

D. Split intervals into smaller parts

Solution

1. Step 1: Understand overlapping intervals

   Intervals overlap if one starts before the other ends. For example, [1,3] and [2,6] overlap because 2 is between 1 and 3.

2. Step 2: Merge overlapping intervals

   We combine overlapping intervals into one that covers the full range, like merging [1,3] and [2,6] into [1,6].

3. Final Answer:

   Combine intervals that overlap into one continuous interval -> Option C

4. Quick Check:

   Merging = Combine overlaps [OK]

Hint: Merge intervals by combining overlapping ranges [OK]

Common Mistakes:

• Only sorting by end values
• Removing instead of merging overlaps
• Splitting intervals unnecessarily

2. Which Go code snippet correctly sorts intervals by their start value before merging?

easy

A. sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })

B. sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] > intervals[j][0] })

C. sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] < intervals[j][1] })

D. sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] > intervals[j][1] })

Solution

1. Step 1: Identify sorting by start value

   We want to sort intervals by their first element (start), so the comparison should be intervals[i][0] < intervals[j][0].

2. Step 2: Match with Go sort.Slice syntax

   sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] }) uses sort.Slice with the correct comparison function for start values.

3. Final Answer:

   sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] }) -> Option A

4. Quick Check:

   Sort by start = sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] }) [OK]

Hint: Sort intervals by start using intervals[i][0] < intervals[j][0] [OK]

Common Mistakes:

• Sorting by end value instead of start
• Using greater than instead of less than
• Mixing start and end indices

3. What is the output of the following Go code that merges intervals?

package main
import (
  "fmt"
  "sort"
)
func merge(intervals [][]int) [][]int {
  if len(intervals) == 0 {
    return intervals
  }
  sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
  merged := [][]int{intervals[0]}
  for i := 1; i < len(intervals); i++ {
    last := merged[len(merged)-1]
    if intervals[i][0] <= last[1] {
      if intervals[i][1] > last[1] {
        last[1] = intervals[i][1]
      }
    } else {
      merged = append(merged, intervals[i])
    }
  }
  return merged
}
func main() {
  intervals := [][]int{{1,3},{2,4},{5,7},{6,8}}
  fmt.Println(merge(intervals))
}

medium

A. [[1 3] [2 4] [5 7] [6 8]]

B. [[1 3] [5 8]]

C. [[1 4] [5 7]]

D. [[1 4] [5 8]]

Solution

1. Step 1: Sort intervals by start

   Intervals sorted: [[1,3],[2,4],[5,7],[6,8]] (already sorted).

2. Step 2: Merge overlapping intervals

   [1,3] and [2,4] overlap, merged to [1,4]. [5,7] and [6,8] overlap, merged to [5,8]. Final merged list: [[1,4],[5,8]].

3. Final Answer:

   [[1 4] [5 8]] -> Option D

4. Quick Check:

   Merged intervals = [[1 4] [5 8]] [OK]

Hint: Sort then merge by comparing current start with last merged end [OK]

Common Mistakes:

• Not updating the end value when merging
• Appending intervals without checking overlap
• Incorrect sorting order

4. Find the error in this Go code snippet for merging intervals:

func merge(intervals [][]int) [][]int {
  sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
  merged := [][]int{}
  for _, interval := range intervals {
    if len(merged) == 0 || merged[len(merged)-1][1] < interval[0] {
      merged = append(merged, interval)
    } else {
      merged[len(merged)-1][1] = interval[1]
    }
  }
  return merged
}

medium

A. Does not sort intervals before merging

B. Does not check if new interval end is greater before updating

C. Appends intervals without checking overlap

D. Returns original intervals instead of merged

Solution

1. Step 1: Review merging logic

   The code updates the end of last merged interval directly with interval[1] without checking if it's greater.

2. Step 2: Identify missing condition

   It should update only if interval[1] > merged[len(merged)-1][1] to avoid shrinking the interval.

3. Final Answer:

   Does not check if new interval end is greater before updating -> Option B

4. Quick Check:

   Update end only if greater [OK]

Hint: Update merged end only if new interval end is larger [OK]

Common Mistakes:

• Overwriting end without comparison
• Skipping sorting step
• Appending without overlap check

5. Given intervals [[1,4],[4,5],[7,9],[8,10],[12,15]], what is the merged output if intervals that touch at endpoints are considered overlapping?

hard

A. [[1 5] [7 10] [12 15]]

B. [[1 4] [4 5] [7 10] [12 15]]

C. [[1 5] [7 9] [8 10] [12 15]]

D. [[1 4] [7 10] [12 15]]

Solution

1. Step 1: Understand touching intervals as overlapping

   Intervals like [1,4] and [4,5] touch at 4, so they merge into [1,5]. Similarly, [7,9] and [8,10] overlap and merge into [7,10].

2. Step 2: Merge all overlapping/touching intervals

   After merging, intervals become [[1,5],[7,10],[12,15]].

3. Final Answer:

   [[1 5] [7 10] [12 15]] -> Option A

4. Quick Check:

   Touching intervals merge = [[1 5] [7 10] [12 15]] [OK]

Hint: Treat touching intervals as overlapping to merge [OK]

Common Mistakes:

• Not merging intervals that touch at endpoints
• Leaving touching intervals separate
• Incorrectly merging non-overlapping intervals