Non Overlapping Intervals Minimum Removal in DSA Java - Time & Space Complexity

Time Complexity: Non Overlapping Intervals Minimum Removal

O(n log n)

Understanding Time Complexity

We want to find out how the time needed to remove overlapping intervals grows as the number of intervals increases.

How does the program's work change when we have more intervals to check?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import java.util.Arrays;
import java.util.Comparator;

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) return 0;
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[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];
        }
    }
    return count;
}
    

This code sorts intervals by their end time and counts how many intervals must be removed to avoid overlaps.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the intervals array.
• How many times: Sorting takes multiple comparisons depending on the number of intervals (n).
• Secondary operation: One loop through the intervals after sorting.
• How many times: The loop runs once for each interval (n times).

How Execution Grows With Input

Sorting grows faster than just looping, so it dominates the time needed.

Input Size (n)	Approx. Operations
10	About 10 log 10 (≈33) for sorting + 10 for loop
100	About 100 log 100 (≈664) for sorting + 100 for loop
1000	About 1000 log 1000 (≈9966) for sorting + 1000 for loop

Pattern observation: As input grows, sorting cost grows faster than the simple loop, roughly multiplying by n log n.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a bit faster than just the number of intervals because sorting takes extra work.

Common Mistake

[X] Wrong: "The loop is the main cost, so the time is O(n)."

[OK] Correct: Sorting the intervals takes more time than the loop, so the total time is not just O(n) but O(n log n).

Interview Connect

Understanding how sorting affects time helps you explain your solution clearly and shows you know what part of your code costs the most.

Self-Check

"What if the intervals were already sorted by end time? How would the time complexity change?"

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