Merge Overlapping Intervals in DSA Go - Deep Dive

Overview - Merge Overlapping Intervals

What is it?

Merge Overlapping Intervals is a way to combine intervals that share some common part into one bigger interval. Imagine you have many time slots or ranges, and some of them overlap or touch each other. This method helps you join those overlapping parts so you get fewer, bigger intervals without any overlaps.

Why it matters

Without merging overlapping intervals, you might count the same time or range multiple times, causing confusion or errors. For example, if you schedule meetings that overlap, you might think you have more free time than you actually do. Merging intervals helps organize and simplify data, making it easier to understand and use.

Where it fits

Before learning this, you should understand arrays or lists and how to sort them. After this, you can learn about interval trees or more complex scheduling algorithms that build on merging intervals.

Mental Model

Core Idea

Merging overlapping intervals means combining all intervals that touch or overlap into one continuous interval without gaps.

Think of it like...

It's like putting together puzzle pieces that fit together to form a bigger picture without any empty spaces between them.

Intervals before merging:
[1, 3]  [2, 6]  [8, 10]  [15, 18]

Intervals after merging:
[1, 6]  [8, 10]  [15, 18]

Build-Up - 6 Steps

1

Foundation

Understanding Intervals and Overlaps

Concept: Learn what intervals are and how to tell if two intervals overlap.

An interval is a range between two numbers, like [start, end]. Two intervals overlap if one starts before the other ends and ends after the other starts. For example, [1, 3] and [2, 4] overlap because 2 is between 1 and 3.

Result

You can identify when two intervals share some common part.

Understanding what makes intervals overlap is the base for knowing when to merge them.

2

Foundation

Sorting Intervals by Start Time

Concept: Sort intervals by their start values to prepare for merging.

Before merging, arrange intervals so the one with the smallest start comes first. For example, given intervals [8, 10], [1, 3], [2, 6], sorting them by start gives [1, 3], [2, 6], [8, 10].

Result

Intervals are ordered from earliest start to latest, making it easier to check overlaps in one pass.

Sorting helps process intervals in a logical order, so you only need to look at neighbors to find overlaps.

3

Intermediate

Merging Two Overlapping Intervals

🤔Before reading on: If you have intervals [1, 4] and [3, 5], do you think the merged interval is [1, 5] or [3, 4]? Commit to your answer.

Concept: Combine two intervals that overlap into one interval covering both ranges.

If intervals overlap, the merged interval starts at the smaller start and ends at the larger end. For [1, 4] and [3, 5], merged is [1, 5] because 1 < 3 and 5 > 4.

Result

You get one interval that covers all points from both intervals.

Knowing how to merge two intervals correctly is key to merging many intervals step-by-step.

4

Intermediate

Iterative Merging of Multiple Intervals

🤔Before reading on: When merging multiple intervals, do you think you need to compare every interval with all others, or just with the last merged interval? Commit to your answer.

Concept: Process sorted intervals one by one, merging with the last merged interval if they overlap.

Start with the first interval as merged. For each next interval, check if it overlaps with the last merged interval. If yes, merge them by updating the end. If no, add it as a new merged interval. This way, you only compare with the last merged interval.

Result

A list of merged intervals with no overlaps.

This approach is efficient because it avoids unnecessary comparisons and merges intervals in one pass.

5

Advanced

Implementing Merge Intervals in Go

🤔Before reading on: Do you think the Go code should modify the original intervals or create a new list for merged intervals? Commit to your answer.

Concept: Write Go code that sorts intervals and merges them into a new slice without overlaps.

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 sort.Slice(intervals, func(i, j int) bool { return intervals[i].Start < intervals[j].Start }) merged := []Interval{intervals[0]} for i := 1; i < len(intervals); i++ { last := &merged[len(merged)-1] if intervals[i].Start <= last.End { // Overlap, merge if intervals[i].End > last.End { last.End = intervals[i].End } } else { // No overlap, add new 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) } }

Result

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

Implementing the algorithm in code solidifies understanding and shows how sorting and merging combine to solve the problem efficiently.

6

Expert

Handling Edge Cases and Performance

🤔Before reading on: Do you think intervals with the same start and end (like [2,2]) affect merging? Commit to your answer.

Concept: Consider intervals with zero length, fully contained intervals, and analyze time complexity.

Edge cases include intervals like [2, 2] which represent a single point, or intervals fully inside others like [3, 4] inside [1, 5]. The algorithm naturally handles these by merging or ignoring duplicates. The time complexity is O(n log n) due to sorting; merging is O(n). For very large data, consider interval trees or segment trees for faster queries.

Result

Robust merging that works correctly on all interval types and scales well.

Understanding edge cases prevents bugs in real applications and knowing complexity guides when to use this method or more advanced data structures.

Under the Hood

The algorithm first sorts intervals by their start values so they are in order. Then it walks through the sorted list, keeping track of the last merged interval. If the current interval overlaps with the last merged one, it updates the end of the last merged interval to cover both. Otherwise, it adds the current interval as a new merged interval. This way, it merges all overlapping intervals in one pass after sorting.

Why designed this way?

Sorting first simplifies the problem by ensuring intervals are checked in order, so only the last merged interval needs comparison. This avoids checking every pair, reducing complexity from O(n^2) to O(n log n). Alternatives like checking all pairs are slower and less practical for large data.

Sorted intervals:
┌─────────┐ ┌─────────────┐ ┌───────┐ ┌───────────────┐
│ [1, 3] │ │  [2, 6]     │ │[8,10] │ │   [15, 18]    │
└─────────┘ └─────────────┘ └───────┘ └───────────────┘

Merging process:
Start with [1,3]
Check [2,6]: overlaps with [1,3], merge to [1,6]
Check [8,10]: no overlap, add new
Check [15,18]: no overlap, add new

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

Myth Busters - 4 Common Misconceptions

Quick: Do you think sorting intervals by end time instead of start time works equally well for merging? Commit yes or no.

Common Belief: Sorting intervals by their end time is just as good as sorting by start time for merging.

Reality: Sorting by start time is necessary because merging depends on intervals starting in order. Sorting by end time can miss overlaps or cause incorrect merges.

Why it matters: Using the wrong sort order can cause incorrect merged intervals, leading to wrong results in scheduling or range calculations.

Quick: If two intervals touch at a point like [1,3] and [3,5], do you think they should be merged? Commit yes or no.

Common Belief: Intervals that only touch at a single point are not overlapping and should not be merged.

Reality: Intervals that touch at a point (where end of one equals start of another) are usually merged to form a continuous interval.

Why it matters: Not merging touching intervals can cause fragmented intervals and misrepresent continuous ranges.

Quick: Do you think the original list of intervals is always modified after merging? Commit yes or no.

Common Belief: Merging intervals always changes the original list of intervals.

Reality: The original list can remain unchanged if the algorithm creates a new list for merged intervals, preserving input data.

Why it matters: Modifying input data unexpectedly can cause bugs in programs that rely on original intervals elsewhere.

Quick: Do you think merging intervals is always the fastest way to handle interval queries? Commit yes or no.

Common Belief: Merging intervals is the best approach for all interval-related problems.

Reality: For some problems, like many interval queries or updates, data structures like interval trees are faster and more flexible.

Why it matters: Using merging for all interval problems can lead to inefficient solutions and poor performance in complex applications.

Expert Zone

1

Merging intervals assumes intervals are closed ranges; open or half-open intervals require careful boundary handling.

2

When intervals have additional data (like labels), merging must decide how to combine or preserve that data, which complicates the algorithm.

3

In concurrent or streaming data, merging intervals incrementally requires different approaches than batch processing.

When NOT to use

Do not use simple merging when you need fast dynamic interval queries or updates; instead, use interval trees or segment trees. Also avoid merging if intervals have complex metadata that cannot be combined simply.

Production Patterns

In real systems, merging intervals is used in calendar apps to show free/busy times, in database query optimizations to combine ranges, and in network systems to manage IP address blocks efficiently.

Connections

Interval Trees

Builds-on

Understanding merging intervals helps grasp interval trees, which extend merging to support fast queries and updates on intervals.

Sorting Algorithms

Depends on

Efficient merging relies on sorting intervals first, showing how sorting is a foundational tool in many algorithms.

Project Management Scheduling

Application

Merging overlapping intervals models how project tasks overlap and helps optimize resource allocation and timelines.

Common Pitfalls

#1 Not sorting intervals before merging.

Wrong approach:

func mergeIntervals(intervals []Interval) []Interval {
merged := []Interval{}
for _, current := range intervals {
if len(merged) == 0 {
merged = append(merged, current)
continue
}
last := &merged[len(merged)-1]
if current.Start <= last.End {
if current.End > last.End {
last.End = current.End
}
} else {
merged = append(merged, current)
}
}
return merged
}

Correct approach:

func mergeIntervals(intervals []Interval) []Interval {
if len(intervals) == 0 {
return intervals
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i].Start < intervals[j].Start
})
merged := []Interval{intervals[0]}
for i := 1; i < len(intervals); i++ {
last := &merged[len(merged)-1]
if intervals[i].Start <= last.End {
if intervals[i].End > last.End {
last.End = intervals[i].End
}
} else {
merged = append(merged, intervals[i])
}
}
return merged
}

Root cause:

Skipping sorting causes intervals to be processed out of order, leading to missed overlaps and incorrect merges.

#2 Not merging intervals that only touch at a point.

Wrong approach:

if intervals[i].Start < last.End { // strict less than
// merge
}

Correct approach:

if intervals[i].Start <= last.End { // less than or equal
// merge
}

Root cause:

Using strict inequality misses intervals that share a boundary point, causing fragmented intervals.

#3 Modifying the original intervals slice unexpectedly.

Wrong approach:

func mergeIntervals(intervals []Interval) []Interval {
for i := 1; i < len(intervals); i++ {
if intervals[i].Start <= intervals[i-1].End {
intervals[i-1].End = max(intervals[i-1].End, intervals[i].End)
intervals = append(intervals[:i], intervals[i+1:]...)
i--
}
}
return intervals
}

Correct approach:

func mergeIntervals(intervals []Interval) []Interval {
if len(intervals) == 0 {
return intervals
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i].Start < intervals[j].Start
})
merged := []Interval{intervals[0]}
for i := 1; i < len(intervals); i++ {
last := &merged[len(merged)-1]
if intervals[i].Start <= last.End {
if intervals[i].End > last.End {
last.End = intervals[i].End
}
} else {
merged = append(merged, intervals[i])
}
}
return merged
}

Root cause:

In-place modification with slice operations can cause unexpected behavior and bugs; creating a new merged list is safer.

Key Takeaways

Merging overlapping intervals combines all intervals that touch or overlap into continuous ranges without gaps.

Sorting intervals by their start time is essential to efficiently merge them in one pass.

Comparing each interval only with the last merged interval reduces complexity and simplifies the algorithm.

Edge cases like zero-length intervals or touching boundaries must be handled carefully to avoid errors.

For dynamic or complex interval queries, more advanced data structures like interval trees are better than simple merging.

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