Understanding Non-overlapping Intervals in Java

What We're Solving & Interval Scheduling

Optimizing conflicting events under resource constraints is a fundamental challenge in scheduling algorithms. The Non-overlapping Intervals problem asks us to determine the minimum number of intervals we need to remove from a collection of intervals so that the remaining intervals do not overlap.

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

• Independent Events: The segments [1, 2], [2, 3], and [3, 4] do not overlap with one another (touching at the boundaries is not considered an overlap).
• Collision: The interval [1, 3] conflicts with both [1, 2] and [2, 3].
• Optimal Removal: By removing [1, 3], we obtain three mutually compatible intervals. This represents the minimum possible removals, so the expected output is 1.

This problem is equivalent to the Interval Scheduling Maximization Problem (ISMP), where our goal is to select the largest possible set of mutually compatible intervals. If K is the maximum number of non-overlapping intervals we can retain, the minimum removals required is simply Total Intervals - K.

The Strategy

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

The optimal strategy relies on sorting the intervals by their ending times (O(n log n) time complexity). By sorting based on end values, we make a local greedy choice that leaves the largest possible room for future intervals.

1. End-Time Sorting: We sort the intervals: Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1])).
2. Boundary Tracking: We initialize end to the end time of our first sorted interval, and set a removals counter to 0.
3. Linear Sweep: We traverse the remaining intervals:
   • Conflict Detection: If the current interval's start time is strictly less than our active end boundary, it overlaps. Since sorting guarantees that this current interval ends later than or equal to our active boundary, we choose to remove it and increment our removals counter.
   • Scheduling Success: If the current interval starts at or after our active end boundary, there is no conflict. We update end = intervals[i][1] to track this new boundary.

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.

Detailed Trace Walkthrough

Let's trace this greedy algorithm step-by-step on intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]:

1. Step 1 (Sorting): Sort the array of intervals by their end times:
   • Sorted list: [[1, 2], [2, 3], [1, 3], [3, 4]].
2. Step 2 (Initialize):
   • Set end = 2 (the end boundary of the first interval [1, 2]).
   • Set removals = 0.
3. Step 3 (First Loop Item: [2, 3]):
   • Compare start time: 2 is greater than or equal to the current end boundary 2.
   • No overlap! We successfully schedule [2, 3] and update the end boundary: end = 3.
   • State: end = 3, removals = 0.
4. Step 4 (Second Loop Item: [1, 3]):
   • Compare start time: 1 is strictly less than the active end boundary 3.
   • Overlap detected! We greedily remove this interval: removals = 1.
   • The end boundary remains 3. State: end = 3, removals = 1.
5. Step 5 (Third Loop Item: [3, 4]):
   • Compare start time: 3 is greater than or equal to the active end boundary 3.
   • No overlap! We successfully schedule [3, 4] and update the end boundary: end = 4.
   • State: end = 4, removals = 1.
6. Step 6 (Completion): The loop finishes, and we return our total removals count: 1.

Code Highlights & Explanations

Key highlights of our Java implementation:

• Integer.compare(a[1], b[1]) ensures clean end-time comparison and avoids integer subtraction underflow bugs.
• intervals[i][0] < end detects overlaps. We increment the counter without updating the end boundary, which effectively discards the conflicting interval.

Full Code Solution

Below is the complete, self-contained Java source code that demonstrates this sorting logic, along with a main method for logging the execution steps.

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 & Takeaways

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.