Non Overlapping Intervals Minimum Removal in DSA Go

Mental Model

We want to remove the fewest intervals so that no intervals overlap. We do this by always keeping the interval that ends earliest to leave room for others.

Analogy: Imagine scheduling meetings in one room. To fit the most meetings without clashes, always pick the meeting that finishes earliest, then schedule the next meeting that starts after it ends.

Intervals: [1,3] -> [2,4] -> [3,5] -> [6,7]
Goal: Remove minimum intervals so none overlap.

Dry Run Walkthrough

Input: intervals: [[1,3], [2,4], [3,5], [6,7]]

Goal: Remove the fewest intervals so that remaining intervals do not overlap.

Step 1: Sort intervals by end time

[1,3] -> [2,4] -> [3,5] -> [6,7]

Why: Sorting by end time helps pick intervals that finish earliest first.

Step 2: Keep first interval [1,3], set end = 3

[1,3] ↑ end=3 -> [2,4] -> [3,5] -> [6,7]

Why: Start with earliest finishing interval to maximize space for others.

Step 3: Check [2,4]: start 2 < end 3, overlap found, remove it

[1,3] ↑ end=3 -> [2,4] (removed) -> [3,5] -> [6,7]

Why: Overlap means we must remove one; remove current interval to keep earliest end.

Step 4: Check [3,5]: start 3 >= end 3, keep it, update end=5

[1,3] -> [3,5] ↑ end=5 -> [6,7]

Why: No overlap, so keep interval and update end pointer.

Step 5: Check [6,7]: start 6 >= end 5, keep it, update end=7

[1,3] -> [3,5] -> [6,7] ↑ end=7

Why: No overlap, keep interval.

Result:

[1,3] -> [3,5] -> [6,7]
Minimum removals: 1

Annotated Code

DSA Go

package main

import (
	"fmt"
	"sort"
)

type Interval struct {
	start int
	end   int
}

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

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

	count := 0
	end := intervals[0].end

	for i := 1; i < len(intervals); i++ {
		if intervals[i].start < end {
			count++ // remove current interval
		} else {
			end = intervals[i].end // update end to current interval's end
		}
	}

	return count
}

func main() {
	intervals := []Interval{{1, 3}, {2, 4}, {3, 5}, {6, 7}}
	removals := eraseOverlapIntervals(intervals)
	fmt.Printf("Minimum removals: %d\n", removals)
}

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

Sort intervals by their end time to prioritize earliest finishing intervals

end := intervals[0].end

Initialize end pointer to the end of the first interval

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

Traverse intervals from second to last

if intervals[i].start < end {

Check if current interval overlaps with last kept interval

count++ // remove current interval

Increment removal count because of overlap

else { end = intervals[i].end }

No overlap, update end to current interval's end

Output

Minimum removals: 1

Complexity Analysis

Time: O(n log n) because we sort the intervals first, then traverse them once

Space: O(1) because sorting is done in place and only a few variables are used

vs Alternative: Naive approach checks all pairs for overlap O(n^2), this greedy method is faster and simpler

Edge Cases

empty intervals list

returns 0 removals since no intervals exist

DSA Go

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

all intervals non-overlapping

returns 0 removals because no overlaps exist

DSA Go

if intervals[i].start < end { count++ } else { end = intervals[i].end }

all intervals overlapping

removes all but one interval, returns n-1

DSA Go

count++ // remove current interval

When to Use This Pattern

When asked to remove minimum intervals to avoid overlaps, use a greedy approach sorting by end times to keep earliest finishing intervals.

Common Mistakes

Mistake: Sorting intervals by start time instead of end time
Fix: Sort intervals by their end time to maximize room for future intervals

Mistake: Updating end pointer incorrectly when removing intervals
Fix: Only update end when interval is kept, not when removed

Summary

Removes the fewest intervals so that no intervals overlap.

Use when you want to schedule intervals without clashes by removing minimal intervals.

Always keep the interval that ends earliest to leave space for others.

Practice

1. What is the main goal of the Non Overlapping Intervals Minimum Removal problem?

easy

A. To remove the minimum number of intervals so that the remaining intervals do not overlap

B. To find the maximum number of overlapping intervals

C. To merge all intervals into one big interval

D. To sort intervals by their start time

Solution

1. Step 1: Understand the problem goal

   The problem asks to remove as few intervals as possible so that no two intervals overlap.

2. Step 2: Clarify what non-overlapping means

   Non-overlapping means intervals do not share any common points except possibly at the boundary.

3. Final Answer:

   To remove the minimum number of intervals so that the remaining intervals do not overlap -> Option A

4. Quick Check:

   Minimum removal = no overlaps [OK]

Hint: Focus on removing intervals, not merging or counting overlaps [OK]

Common Mistakes:

• Thinking the goal is to merge intervals
• Confusing maximum overlaps with minimum removals
• Sorting intervals without removing any

2. Which of the following Go code snippets correctly sorts intervals by their end time for solving the minimum removal problem?

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 end time

   We need to sort intervals by their end time ascending to apply greedy approach.

2. Step 2: Check the Go sort.Slice syntax

   sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] < intervals[j][1] }) sorts by intervals[i][1] < intervals[j][1], which is correct for end time ascending.

3. Final Answer:

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

4. Quick Check:

   Sort by end time ascending = sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] < intervals[j][1] }) [OK]

Hint: Sort intervals by end time ascending for greedy removal [OK]

Common Mistakes:

• Sorting by start time instead of end time
• Sorting in descending order by mistake
• Using wrong slice indices

3. What is the output of the following Go code snippet that finds the minimum number of intervals to remove?

package main
import (
  "fmt"
  "sort"
)
func eraseOverlapIntervals(intervals [][]int) int {
  if len(intervals) == 0 {
    return 0
  }
  sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] < intervals[j][1] })
  count := 0
  end := intervals[0][1]
  for i := 1; i < len(intervals); i++ {
    if intervals[i][0] < end {
      count++
    } else {
      end = intervals[i][1]
    }
  }
  return count
}
func main() {
  intervals := [][]int{{1,3},{2,4},{3,5}}
  fmt.Println(eraseOverlapIntervals(intervals))
}

medium

A. 2

B. 1

C. 0

D. 3

Solution

1. Step 1: Sort intervals by end time

   Sorted intervals: [1,3], [2,4], [3,5]

2. Step 2: Count overlaps

   Start with end=3. Interval [2,4] starts at 2 < 3, so count=1. Interval [3,5] starts at 3 ≥ 3, update end=5.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   One overlap removed = 1 [OK]

Hint: Sort by end time, count intervals starting before current end [OK]

Common Mistakes:

• Not sorting intervals before counting
• Counting intervals that do not overlap
• Incorrectly updating end pointer

4. The following Go code is intended to solve the minimum removal problem but has a bug. What is the bug?

func eraseOverlapIntervals(intervals [][]int) int {
  if len(intervals) == 0 {
    return 0
  }
  sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] < intervals[j][1] })
  count := 0
  end := intervals[0][1]
  for i := 1; i < len(intervals); i++ {
    if intervals[i][0] < end {
      count++
    } else {
      end = intervals[i][0]
    }
  }
  return count
}

medium

A. Updating end with intervals[i][0] instead of intervals[i][1] causes wrong comparisons

B. Missing check for empty intervals slice causes runtime error

C. Sorting by start time instead of end time causes incorrect removal count

D. Using count++ inside the loop is incorrect; should decrement count

Solution

1. Step 1: Check sorting and end update

   Sorting by end time is correct, but updating end incorrectly with intervals[i][0] is wrong.

2. Step 2: Explain why end update is wrong

   End should track the end time of last non-overlapping interval, so intervals[i][1] is correct.

3. Final Answer:

   Updating end with intervals[i][0] instead of intervals[i][1] causes wrong comparisons -> Option A

4. Quick Check:

   End must be interval end, not start [OK]

Hint: Update end with interval's end time, not start time [OK]

Common Mistakes:

• Confusing interval start and end when updating end
• Ignoring empty slice check
• Misunderstanding sorting impact

5. Given intervals [[1,2],[2,3],[3,4],[1,3]], what is the minimum number of intervals to remove to make the rest non-overlapping?

hard

A. 2

B. 3

C. 0

D. 1

Solution

1. Step 1: Sort intervals by end time

   Sorted intervals: [1,2], [1,3], [2,3], [3,4]

2. Step 2: Count overlaps and removals

   Start end=2. Interval [1,3] starts at 1 < 2, count=1. Interval [2,3] starts at 2 ≥ 2, update end=3. Interval [3,4] starts at 3 ≥ 3, update end=4.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   One removal needed = 1 [OK]

Hint: Sort by end, remove intervals starting before current end [OK]

Common Mistakes:

• Not sorting intervals before counting
• Removing more intervals than needed
• Miscounting overlaps with boundary intervals