Non Overlapping Intervals Minimum Removal in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to sort intervals by their end time.

DSA Java

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

Drag options to blanks, or click blank then click option'

A0

B1

C2

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using start time index instead of end time index for sorting.

Mixing indices between 'a' and 'b' in comparator.

We sort intervals by their end time, which is at index 1. The blank is for the first interval's end index, so it should be 1.

2fill in blank

medium

Complete the code to count intervals to remove for no overlap.

DSA Java

if (intervals[i][0] < intervals[[1]][1]) count++; else last = i;

Drag options to blanks, or click blank then click option'

Ai - 1

Bi + 1

C0

Dlast

Attempts:

3 left

💡 Hint

Common Mistakes

Using i-1 or i+1 instead of last index.

Comparing wrong interval indices.

We compare the current interval's start with the last non-overlapping interval's end. 'last' stores the index of the last interval kept.

3fill in blank

hard

Fix the error in the loop condition to iterate over all intervals.

DSA Java

for (int i = 1; i [1] intervals.length; i++) {

Drag options to blanks, or click blank then click option'

A<=

B>

C<

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' causes index out of bounds.

Using '>' or '>=' causes loop not to run.

The loop should run while i is less than intervals.length to avoid ArrayIndexOutOfBoundsException.

4fill in blank

hard

Fill both blanks to complete the method signature and return statement.

DSA Java

public int [1](int[][] intervals) {
    if (intervals.length == 0) return [2];
    // method body
}

Drag options to blanks, or click blank then click option'

AeraseOverlapIntervals

B0

CremoveIntervals

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong method name.

Returning -1 instead of 0 for empty input.

The method name is 'eraseOverlapIntervals' and returns 0 if no intervals exist.

5fill in blank

hard

Fill all three blanks to complete the main logic for counting removals.

DSA Java

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

Drag options to blanks, or click blank then click option'

A1

B0

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting by start time instead of end time.

Using wrong loop condition causing errors.

Sort by end time (index 1), loop while i < intervals.length.

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