Merge Overlapping Intervals in DSA Go - Execution Trace

Concept Flow - Merge Overlapping Intervals

Sort intervals by start

↓

Initialize merged list with first interval

↓

For each next interval

↓

Check overlap with last merged interval?

↓

Merge intervals

↓

Repeat

↓

Done

Sort intervals first, then go through each interval to merge if overlapping or add if not.

Execution Sample

DSA Go

intervals := [][]int{{1,3},{2,6},{8,10},{15,18}}
merged := merge(intervals)
fmt.Println(merged)

Merges overlapping intervals from the input list and prints the merged intervals.

Execution Table

Step	Operation	Current Interval	Last Merged Interval	Action	Merged List State
1	Sort intervals	[1,3],[2,6],[8,10],[15,18]	N/A	Sorted by start	[[1,3],[2,6],[8,10],[15,18]]
2	Initialize merged	[1,3]	N/A	Add first interval	[[1,3]]
3	Check overlap	[2,6]	[1,3]	Overlap: merge to [1,6]	[[1,6]]
4	Check overlap	[8,10]	[1,6]	No overlap: add [8,10]	[[1,6],[8,10]]
5	Check overlap	[15,18]	[8,10]	No overlap: add [15,18]	[[1,6],[8,10],[15,18]]
6	Done	N/A	N/A	All intervals processed	[[1,6],[8,10],[15,18]]

💡 All intervals processed, merged list contains non-overlapping intervals.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
intervals	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]
merged	[]	[[1,3]]	[[1,6]]	[[1,6],[8,10]]	[[1,6],[8,10],[15,18]]	[[1,6],[8,10],[15,18]]
current interval	N/A	[2,6]	[8,10]	[15,18]	N/A	N/A
last merged interval	N/A	[1,3]	[1,6]	[8,10]	[15,18]	N/A

Key Moments - 3 Insights

Why do we sort intervals before merging?

Sorting ensures intervals are in order by start time, so overlapping intervals come one after another. See Step 1 in execution_table.

How do we know if two intervals overlap?

If the current interval's start is less than or equal to the last merged interval's end, they overlap. See Step 3 where [2,6] overlaps with [1,3].

What happens if intervals do not overlap?

We add the current interval as a new separate interval in merged list. See Steps 4 and 5 where [8,10] and [15,18] are added separately.

Visual Quiz - 3 Questions

Look at the execution_table, what is the merged list after Step 3?

A [[2,6]]

B [[1,3],[2,6]]

C [[1,6]]

D [[1,3]]

💡 Hint

Check the 'Merged List State' column at Step 3 in execution_table.

At which step does the condition for no overlap first occur?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the 'Action' column in execution_table where intervals are added without merging.

If the input intervals were not sorted, how would the merged list state change at Step 2?

A It would contain the first unsorted interval

B It would contain all intervals merged

C It would be empty

D It would cause an error

💡 Hint

Refer to variable_tracker for 'merged' variable after Step 2.

Concept Snapshot

Merge Overlapping Intervals:
1. Sort intervals by start time.
2. Initialize merged list with first interval.
3. For each next interval, check overlap with last merged.
4. If overlap, merge by updating end.
5. Else, add interval to merged list.
Result: merged list with no overlapping intervals.

Full Transcript

To merge overlapping intervals, first sort the intervals by their start times. Then start with the first interval in a new merged list. For each next interval, check if it overlaps with the last interval in the merged list by comparing start and end times. If they overlap, merge them by updating the end time of the last merged interval. If not, add the current interval as a new entry. Continue until all intervals are processed. The final merged list contains intervals with no overlaps.

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