Merge Overlapping Intervals in DSA Go - Build from Scratch

Merge Overlapping Intervals

📖 Scenario: You are working on a calendar app that manages meeting times. Sometimes, meetings overlap and you want to combine those overlapping meetings into one to avoid confusion.

🎯 Goal: Build a program that takes a list of meeting time intervals and merges all overlapping intervals into one.

📋 What You'll Learn

Create a slice of intervals with exact values

Add a variable to hold the merged intervals

Write logic to merge overlapping intervals

Print the merged intervals in the specified format

💡 Why This Matters

🌍 Real World

Merging overlapping intervals is useful in calendar apps, booking systems, and timeline visualizations to simplify overlapping time slots.

💼 Career

Understanding interval merging is important for software engineers working on scheduling, resource allocation, and data processing tasks.

1

Create the initial intervals slice

Create a slice of intervals called intervals with these exact values: {1, 3}, {2, 6}, {8, 10}, {15, 18}. Use a struct type Interval with start and end fields of type int.

DSA Go

package main

import "fmt"

type Interval struct {
    start int
    end   int
}

func main() {
    // Create the intervals slice here

}

Hint

Define the slice with the exact intervals as shown.

2

Add a variable to hold merged intervals

Add a variable called merged of type slice of Interval to hold the merged intervals. Initialize it as an empty slice.

DSA Go

package main

import "fmt"

type Interval struct {
    start int
    end   int
}

func main() {
    intervals := []Interval{{1, 3}, {2, 6}, {8, 10}, {15, 18}}
    // Create merged slice here

}

Hint

Initialize merged as an empty slice of Interval.

3

Write logic to merge overlapping intervals

Write a for loop to iterate over intervals. For each interval, if merged is empty or the last interval in merged does not overlap with interval, append interval to merged. Otherwise, merge by updating the end of the last interval in merged to the maximum of its current end and interval.end.

DSA Go

package main

import "fmt"

type Interval struct {
    start int
    end   int
}

func main() {
    intervals := []Interval{{1, 3}, {2, 6}, {8, 10}, {15, 18}}
    merged := []Interval{}
    // Merge intervals here

}

Hint

Check if merged is empty or no overlap, then append. Else update the end of last merged interval.

4

Print the merged intervals

Print the merged slice in the format: each interval as {start,end} separated by spaces on one line.

DSA Go

package main

import "fmt"

type Interval struct {
    start int
    end   int
}

func main() {
    intervals := []Interval{{1, 3}, {2, 6}, {8, 10}, {15, 18}}
    merged := []Interval{}

    for _, interval := range intervals {
        if len(merged) == 0 || merged[len(merged)-1].end < interval.start {
            merged = append(merged, interval)
        } else {
            if merged[len(merged)-1].end < interval.end {
                merged[len(merged)-1].end = interval.end
            }
        }
    }
    // Print merged intervals here
}

Hint

Use a loop to print each merged interval in the format {start,end} separated by spaces.

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