Understanding Non-overlapping Intervals in Java

Introduction & Problem Explanation

The Non-overlapping Intervals problem asks us to find the minimum number of intervals we need to remove from a given collection of intervals so that the remaining intervals do not overlap.

An interval is represented as a pair [start, end]. For example, if the input is [[1, 2], [2, 3], [3, 4], [1, 3]]:

• Intervals [1, 2], [2, 3], and [3, 4] do not overlap at their boundaries.
• Interval [1, 3] overlaps with both [1, 2] and [2, 3].
• By removing [1, 3], we are left with 3 non-overlapping intervals. This is the minimum possible number of removals, so we return 1.

This problem is equivalent to the classic Interval Scheduling Maximization Problem (ISMP), where we want to schedule the maximum number of mutually compatible events. By finding the maximum number of non-overlapping intervals we can keep (let this be K), the minimum number of removals is simply Total Intervals - K.

The Algorithmic Approach

Greedy Sorting by End Time (O(n) Time, O(1) Space)

The greedy rule for maximizing independent intervals is to **always select the interval that ends earliest**. Here is our approach:

1. Sort: We sort the intervals based on their end times: a[1] - b[1].
2. Track End Boundary: We maintain a variable end representing the end time of the last successfully scheduled interval, initialized to the end time of the first sorted interval. We also maintain a counter removals = 0.
3. Scan and Count: For each subsequent interval i:
   • If the start time of interval i is less than our active end boundary (intervals[i][0] < end), they overlap. Since we are greedily keeping the interval that ends earlier, we choose to remove this current interval. We increment removals++.
   • Otherwise, they do not overlap. We successfully schedule interval i by updating our active boundary: end = intervals[i][1].

Sorting takes O(n log n) time, and the linear sweep takes O(n). Space complexity is O(1) if we sort the input array in place.

Step-by-Step Execution Walkthrough

Let's trace the algorithm with intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]:

1. Step 1 (Sorting): Sort the intervals based on their end times.
   • Sorted: [[1, 2], [2, 3], [1, 3], [3, 4]].
2. Step 2 (Initialize):
   • Set end = 2 (end time of the first interval [1, 2]).
   • Set removals = 0.
3. Step 3 (Interval 1: [2, 3]):
   • Compare start: intervals[1][0] = 2. Since 2 >= end (2), there is no overlap.
   • Schedule it: Update end = 3.
   • State: end = 3, removals = 0.
4. Step 4 (Interval 2: [1, 3]):
   • Compare start: intervals[2][0] = 1. Since 1 < end (3), they overlap!
   • Greedy removal: Increment removals = 1.
   • State: end = 3, removals = 1.
5. Step 5 (Interval 3: [3, 4]):
   • Compare start: intervals[3][0] = 3. Since 3 >= end (3), there is no overlap.
   • Schedule it: Update end = 4.
   • State: end = 4, removals = 1.
6. Step 6 (Result): Loop ends. We return removals = 1.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));: The foundation of the greedy strategy. Sorting by end time ensures that we always evaluate options that vacate our resource earliest.
• if (intervals[i][0] < end) removals++;: Identifies an overlap. Since the current interval ends later than or equal to our active boundary (due to sorting), we greedily discard the current interval to keep the smaller end boundary.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.Arrays;

public class NonOverlappingIntervals {

    // Greedy End-Time Sort: Time O(N log N), Space O(1)
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }

        // Sort intervals by their end times (index 1)
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int count = 0;
        int end = intervals[0][1]; // End time of the last scheduled interval

        for (int i = 1; i < intervals.length; i++) {
            // If the start time of the current interval is less than the active end, they overlap
            if (intervals[i][0] < end) {
                count++; // Increment the number of intervals to remove
            } else {
                // Otherwise, they do not overlap, schedule this interval and update the end time
                end = intervals[i][1];
            }
        }

        return count;
    }

    public static void main(String[] args) {
        NonOverlappingIntervals solver = new NonOverlappingIntervals();
        int[][] intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};

        System.out.println("--- Non-overlapping Intervals Demonstration ---");
        System.out.println("Input Intervals: " + Arrays.deepToString(intervals));
        int removals = solver.eraseOverlapIntervals(intervals);
        System.out.println("Minimum intervals to remove: " + removals); // Expected: 1
    }
}

Conclusion

The Non-overlapping Intervals problem highlights how a change of perspective (sorting by end time instead of start time) simplifies a scheduling problem. With this greedy choice, we solve the problem optimally in O(n log n) time.