Non Overlapping Intervals Minimum Removal in DSA Java - Build from Scratch

Non Overlapping Intervals Minimum Removal

📖 Scenario: You are organizing a schedule with several time intervals. Some intervals overlap, and you want to remove the minimum number of intervals so that the remaining intervals do not overlap.This is like planning meetings in a room where no two meetings can happen at the same time.

🎯 Goal: Build a Java program that finds the minimum number of intervals to remove so that the rest do not overlap.

📋 What You'll Learn

Create an array of intervals with exact values

Add a variable to count removals

Implement the logic to find minimum removals for non-overlapping intervals

Print the minimum number of intervals to remove

💡 Why This Matters

🌍 Real World

Scheduling meetings, booking rooms, or planning events where overlapping times are not allowed.

💼 Career

Common problem in software engineering interviews and real-world applications involving time management and resource allocation.

1

Create the intervals array

Create a 2D integer array called intervals with these exact intervals: {1, 3}, {2, 4}, {3, 5}, {6, 7}, {8, 10}, {9, 11}

DSA Java

// Your code here

Hint

Use a 2D array with exact intervals as shown.

2

Add a variable to count removals

Create an integer variable called removals and set it to 0

DSA Java

int[][] intervals = {{1, 3}, {2, 4}, {3, 5}, {6, 7}, {8, 10}, {9, 11}};
// Your code here

Hint

Initialize removals to zero before processing intervals.

3

Implement the minimum removal logic

Sort the intervals array by the end time of each interval using Arrays.sort(intervals, (a, b) -> a[1] - b[1]). Then use a for loop with variable i from 1 to intervals.length - 1. Inside the loop, compare the start time of intervals[i] with the end time of intervals[i - 1]. If they overlap, increment removals by 1 and update intervals[i][0] to intervals[i - 1][0] to keep the interval with the earlier end time.

DSA Java

int[][] intervals = {{1, 3}, {2, 4}, {3, 5}, {6, 7}, {8, 10}, {9, 11}};
int removals = 0;
// Your code here

Hint

Sort intervals by end time, then check overlaps to count removals.

4

Print the minimum number of removals

Write System.out.println(removals); to print the minimum number of intervals to remove

DSA Java

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {2, 4}, {3, 5}, {6, 7}, {8, 10}, {9, 11}};
        int removals = 0;
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                removals++;
                intervals[i][0] = intervals[i - 1][0];
            }
        }
        // Print the removals
        // Your code here
    }
}

Hint

Use System.out.println(removals); to show the result.

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