Non Overlapping Intervals Minimum Removal in DSA Java

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]
We want to remove overlaps so the timeline looks like:
[1,3] -> [3,5] -> [6,7]
No overlaps remain.

Dry Run Walkthrough

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

Goal: Remove minimum intervals so no two intervals 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 to maximize non-overlapping intervals

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

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

Why: Start with earliest finishing interval to compare others against

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

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

Why: Overlap detected, remove interval to avoid clash

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

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

Why: No overlap, update end to current interval's end

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

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

Why: No overlap, update end to current interval's end

Result:

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

Annotated Code

DSA Java

import java.util.*;

public class NonOverlappingIntervals {
    static class Interval {
        int start, end;
        Interval(int s, int e) { start = s; end = e; }
    }

    public static int eraseOverlapIntervals(Interval[] intervals) {
        if (intervals.length == 0) return 0;
        Arrays.sort(intervals, Comparator.comparingInt(i -> i.end));
        int end = intervals[0].end;
        int count = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start < end) {
                count++; // remove overlapping interval
            } else {
                end = intervals[i].end; // update end to current interval's end
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Interval[] intervals = {
            new Interval(1, 3),
            new Interval(2, 4),
            new Interval(3, 5),
            new Interval(6, 7)
        };
        int removed = eraseOverlapIntervals(intervals);
        System.out.println("Minimum intervals removed: " + removed);
    }
}

Arrays.sort(intervals, Comparator.comparingInt(i -> i.end));

Sort intervals by their end time to prioritize earliest finishing

int end = intervals[0].end;

Initialize end to the end of first interval to compare others

if (intervals[i].start < end) {

Check if current interval overlaps with last kept interval

count++; // remove overlapping interval

Increment removal count for overlapping interval

else { end = intervals[i].end; }

Update end to current interval's end if no overlap

Output

Minimum intervals removed: 1

Complexity Analysis

Time: O(n log n) because we sort the intervals by end time, then traverse once

Space: O(1) because sorting is 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 much faster

Edge Cases

empty intervals array

returns 0 since no intervals to remove

DSA Java

if (intervals.length == 0) return 0;

all intervals non-overlapping

returns 0 since no removals needed

DSA Java

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

all intervals overlapping

removes all but one interval

DSA Java

if (intervals[i].start < end) { count++; }

When to Use This Pattern

When asked to remove minimum intervals to avoid overlap, use a greedy approach by sorting intervals by end time and removing intervals that start before the last kept interval ends.

Common Mistakes

Mistake: Sorting intervals by start time instead of end time
Fix: Sort intervals by their end time to ensure earliest finishing intervals are chosen first

Mistake: Not updating the end pointer after keeping an interval
Fix: Update end to current interval's end when no overlap is found

Summary

Removes the minimum number of intervals to ensure no overlaps remain.

Use when you want to schedule intervals without conflicts by removing as few as possible.

Always pick intervals that finish earliest to maximize room for others and minimize removals.

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