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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of minimum removals for overlapping intervals

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

DSA Java

import java.util.*;

public class Solution {
    public static int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        int count = 0;
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                count++;
            } else {
                end = intervals[i][1];
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,4},{3,5},{6,7}};
        System.out.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 their end time. It keeps track of the end of the last added interval. If the next interval starts before this end, it counts as an overlap and increments removal count. Here, only one interval overlaps.

🧠 Conceptual

intermediate

Understanding the greedy choice in interval removal

Why does sorting intervals by their end time help in minimizing the number of intervals to remove to avoid overlaps?

A It sorts intervals randomly to check all possibilities.

B It groups all overlapping intervals together for easy removal.

C It sorts intervals by their start time to remove the earliest starting intervals first.

D It ensures we always keep the interval that ends earliest, leaving more room for others.

💡 Hint

Think about how choosing intervals that finish early affects the rest.

Choosing intervals that end earliest leaves maximum space for the remaining intervals, reducing overlaps and removals.

🔧 Debug

advanced

Identify the error in interval removal code

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

DSA Java

import java.util.*;

public class Solution {
    public static int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int count = 0;
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                count++;
            } else {
                end = intervals[i][1];
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] intervals = {};
        System.out.println(eraseOverlapIntervals(intervals));
    }
}

A No output, program runs successfully and prints 0

B ArrayIndexOutOfBoundsException because intervals array is empty

C NullPointerException due to uninitialized array

D Compilation error due to lambda syntax

💡 Hint

Check what happens when intervals length is zero.

The code accesses intervals[0][1] without checking if intervals is empty, causing ArrayIndexOutOfBoundsException.

❓ Predict Output

advanced

Output of minimum removals with overlapping intervals

What is the output of this Java code that finds the minimum number of intervals to remove?

DSA Java

import java.util.*;

public class Solution {
    public static int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
        int count = 0;
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                count++;
            } else {
                end = intervals[i][1];
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,2},{2,3},{3,4},{1,3}};
        System.out.println(eraseOverlapIntervals(intervals));
    }
}

A 1

B 2

C 3

D 0

💡 Hint

Sort by end time and count overlaps.

Only the interval {1,3} overlaps with others and needs removal.

🚀 Application

expert

Minimum removals for large interval set

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

A 999999

B 0

C 500000

D 1

💡 Hint

Consider how intervals overlap and how many can fit without overlapping.

Each interval overlaps with the next one. We can keep every other interval to avoid overlaps, so half must be removed.

Practice

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

easy

A. To find the maximum number of overlapping intervals

B. To find the minimum number of intervals to remove so that the rest do not overlap

C. To sort intervals by their start time

D. To merge all overlapping intervals into one

Solution

1. Step 1: Understand the problem goal

   The problem asks to remove the fewest intervals so that no two intervals overlap.

2. Step 2: Differentiate from related problems

   Unlike merging intervals or counting overlaps, here we minimize removals to avoid overlaps.

3. Final Answer:

   To find the minimum number of intervals to remove so that the rest do not overlap -> Option B

4. Quick Check:

   Minimum removals = no overlaps [OK]

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

Common Mistakes:

• Confusing with merging intervals problem
• Thinking the goal is to count overlaps
• Assuming sorting alone solves the problem

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

easy

A. Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

B. Arrays.sort(intervals, (a, b) -> b[1] - a[1]);

C. Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

D. Arrays.sort(intervals);

Solution

1. Step 1: Identify sorting criteria for greedy approach

   We sort intervals by their end time ascending to pick earliest finishing intervals first.

2. Step 2: Match code to sorting by end time ascending

   Arrays.sort(intervals, (a, b) -> a[1] - b[1]); uses comparator (a, b) -> a[1] - b[1], which sorts by end time ascending.

3. Final Answer:

   Arrays.sort(intervals, (a, b) -> a[1] - b[1]); -> Option C

4. Quick Check:

   Sort by end time ascending = Arrays.sort(intervals, (a, b) -> a[1] - b[1]); [OK]

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

Common Mistakes:

• Sorting by start time instead of end time
• Sorting in descending order of end time
• Using default sort without comparator for 2D array

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

int[][] intervals = {{1,3},{2,4},{3,5}};
Arrays.sort(intervals, (a,b) -> a[1] - b[1]);
int count = 0, end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
  if (intervals[i][0] < end) {
    count++;
  } else {
    end = intervals[i][1];
  }
}
System.out.println(count);

medium

A. 1

B. 0

C. 2

D. 3

Solution

1. Step 1: Sort intervals by end time

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

2. Step 2: Iterate and count overlaps

   Start with end=3. Check [2,4]: 2 < 3 overlap, count=1. Check [3,5]: 3 < 3 false, update end=5.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   One overlap removed = 1 [OK]

Hint: Count intervals starting before current end to find removals [OK]

Common Mistakes:

• Not updating end when no overlap
• Counting non-overlapping intervals as removals
• Incorrectly sorting intervals

4. Identify the bug in the following Java code that attempts to solve the minimum removal problem:

int[][] intervals = {{1,2},{2,3},{3,4},{1,3}};
Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
int count = 0, end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
  if (intervals[i][0] < end) {
    count++;
  } else {
    end = intervals[i][1];
  }
}
System.out.println(count);

medium

A. Missing check for empty intervals array

B. Not initializing count to 1 causes wrong output

C. Using < instead of <= in if condition causes errors

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

Solution

1. Step 1: Check sorting criteria

   The code sorts intervals by start time, but greedy approach requires sorting by end time.

2. Step 2: Understand impact on counting removals

   Sorting by start time can cause wrong overlap detection and incorrect removal count.

3. Final Answer:

   Sorting by start time instead of end time causes incorrect removal count -> Option D

4. Quick Check:

   Sort by end time, not start time [OK]

Hint: Always sort by end time for correct greedy removal count [OK]

Common Mistakes:

• Sorting by start time instead of end time
• Confusing overlap condition with equality
• Ignoring empty input edge case

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

hard

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Sort intervals by end time ascending

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

2. Step 2: Select intervals greedily and count removals

   Pick [1,2], end=2. [2,3] start=2 ≥ 2 no removal, end=3. [1,3] start=1 < 3 removal=1. [3,4] start=3 ≥ 3 no removal, end=4. [2,5] start=2 < 4 removal=2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Two removals needed = 2 [OK]

Hint: Sort by end time, pick earliest finishing intervals, count overlaps [OK]

Common Mistakes:

• Not sorting by end time before processing
• Counting intervals that do not overlap as removals
• Forgetting to update end after selecting interval