Non Overlapping Intervals Minimum Removal in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of minimum removals for overlapping intervals

What is the output of the following Go code that calculates the minimum number of intervals to remove to make the rest non-overlapping?

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++
		} else {
			end = intervals[i].end
		}
	}

	return count
}

func main() {
	intervals := []Interval{{1, 3}, {2, 4}, {3, 5}, {6, 7}}
	fmt.Println(eraseOverlapIntervals(intervals))
}

A 1

B 2

C 3

D 0

💡 Hint

Sort intervals by their end time and count overlaps.

The code sorts intervals by end time and counts how many intervals overlap with the previous chosen interval. Only one interval needs removal to avoid overlaps.

❓ Predict Output

intermediate

Result after removing minimum intervals

Given the intervals, what is the count of intervals remaining after removing the minimum number to avoid overlaps?

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++
		} else {
			end = intervals[i].end
		}
	}

	return len(intervals) - count
}

func main() {
	intervals := []Interval{{1, 2}, {2, 3}, {3, 4}, {1, 3}}
	fmt.Println(eraseOverlapIntervals(intervals))
}

A 2

B 1

C 3

D 4

💡 Hint

Calculate total intervals minus minimum removals.

The code returns total intervals minus the count of removals needed. Here, only one interval overlaps, so 4 - 1 = 3 remain.

🧠 Conceptual

advanced

Why sort intervals by end time in minimum removal problem?

Why is sorting intervals by their end time the best approach to minimize the number of intervals removed to avoid overlaps?

A Because sorting by end time groups overlapping intervals together.

B Because sorting by start time always leads to the minimum removals.

C Because sorting by interval length guarantees the fewest removals.

D Because choosing intervals with earliest end time leaves more room for following intervals, minimizing removals.

💡 Hint

Think about how choosing intervals affects space for others.

Sorting by end time allows greedy selection of intervals that finish earliest, maximizing space for others and minimizing removals.

🔧 Debug

advanced

Identify the bug in interval removal code

What error will the following Go code produce when run, and why?

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].start < intervals[j].start
	})

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

	for i := 1; i < len(intervals); i++ {
		if intervals[i].start < end {
			count++
		} else {
			end = intervals[i].end
		}
	}

	return count
}

func main() {
	intervals := []Interval{{1,5}, {2,3}, {3,4}}
	fmt.Println(eraseOverlapIntervals(intervals))
}

A The code runs and outputs 2, but this is incorrect for minimum removals.

B The code runs and outputs 2, which is the correct minimum removals.

C The code panics due to index out of range error.

D The code runs and outputs 0, which is incorrect.

💡 Hint

Check the sorting criteria and how it affects overlap counting.

Sorting by start time instead of end time causes the greedy approach to fail, producing wrong count (2 instead of 1) though code runs without error.

🚀 Application

expert

Minimum removals for large interval set

Given 1,000 intervals where each interval i is [i, i+2], what is the minimum number of intervals to remove to make the rest non-overlapping?

A 334

B 500

C 667

D 999

💡 Hint

Intervals overlap with next one; think about maximum non-overlapping intervals.

Each interval overlaps with the next one. Maximum non-overlapping intervals can be selected by picking every other interval, keeping 500 and removing 500.

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