Non overlapping Intervals

XXX. Remove Overlapping Intervals

Greedy

Interval

Sorting

Problem Statement:

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

• Intervals are represented as [start, end]
• Two intervals overlap if they share any common points
• Return minimum number of intervals to remove

Algorithm:

1. **Greedy Approach**:
   • Sort intervals by end time
   • Keep track of last valid end time
   • Count non-overlapping intervals
2. **Process**:
   • Start with first interval
   • Pick next non-overlapping interval
   • Subtract count from total length

Implementation:

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) 
        return 0;
    
    // Sort by end time for greedy approach
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
    
    int end = intervals[0][1];           // Track last valid end time
    int count = 1;                       // Count of non-overlapping intervals
    
    // Count non-overlapping intervals
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= end) {    // No overlap
            end = intervals[i][1];        // Update end time
            count++;                      // Increment count
        }
    }
    
    return intervals.length - count;      // Return minimum removals needed
}

Complexity:

Time Complexity: O(n log n) due to sorting
Space Complexity: O(1) or O(n) depending on sorting implementation

Example:

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

• Sort by end time: [[1,3], [2,4], [3,5], [4,6]]
• Process intervals:
  • Take [1,3], end = 3, count = 1
  • Skip [2,4] (overlaps)
  • Take [3,5], end = 5, count = 2
  • Skip [4,6] (overlaps)
• Result: 4 (total) - 2 (non-overlapping) = 2 intervals to remove

Key Points:

• **Sorting Strategy**:
  • Sort by end time is crucial for greedy approach
  • Allows picking intervals that leave more room
  • Lambda comparator for clean sorting
• **Interval Selection**:
  • Track end time of last picked interval
  • Pick next interval only if start ≥ previous end
  • Count gives maximum non-overlapping intervals