This post is completed by 2 users

  • 1
 Add to List
Medium

560. Minimum Interval Removal Problem - Leetcode

Problem Statement

Given an array of intervals, where each interval is represented as intervals[i] = [starti, endi], the goal is to determine the minimum number of intervals to remove to make the rest of the intervals non-overlapping.

Key Points:

  • Intervals that touch at a single point (e.g., [1, 2] and [2, 3]) are considered non-overlapping.
  • You must ensure that the remaining intervals do not overlap.

Examples:

Example 1: 
Input: intervals = [[1, 4], [3, 5], [5, 6], [2, 3]]
Output: 1
Explanation: Removing [1, 4] makes the intervals non-overlapping.
Example 2: 
Input: intervals = [[2, 3], [2, 3], [2, 3], [4, 5]]
Output: 2
Explanation: Removing two intervals [2, 3] makes the rest non-overlapping.
Example 3: 
Input: intervals = [[1, 2], [2, 3], [3, 4]]
Output: 0
Explanation: The intervals are already non-overlapping.

Approach to Solve the Problem

This problem can be solved using a greedy algorithm. The key idea is to minimize overlap by always selecting intervals that end the earliest.

Steps:

  1. Sort intervals by their end times: This ensures we always process intervals with earlier end times first, maximizing room for subsequent intervals.
  2. Iterate through the sorted intervals: Track the previous interval and compare it with the current one.
  3. Count overlapping intervals: If the current interval starts before the previous interval ends, increment a counter. Otherwise, update the previous interval.

Code:

 



import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

public class Main {
    public static int eraseOverlapIntervals(int[][] intervals) {
        // Step 1: Sort intervals by their end times
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int count = 0; // Initialize the count of intervals to remove
        int[] prev = intervals[0]; // Start with the first interval

        // Step 2: Iterate through the sorted intervals
        for (int i = 1; i < intervals.length; i++) {
            int[] curr = intervals[i]; // Current interval

            // Step 3: Check for overlap
            if (prev[1] > curr[0]) {
                // Overlap detected, increment the count
                count++;
            } else {
                // No overlap, update previous interval
                prev = curr;
            }
        }

        return count;
    }

    public static void main(String[] args) {

        // Convert test cases to Java-friendly format
        int[][] intervals1 = {{1, 4}, {3, 5}, {5, 6}, {2, 3}};
        System.out.println(eraseOverlapIntervals(intervals1)); // Output: 1

        int[][] intervals2 = {{2, 3}, {2, 3}, {2, 3}, {4, 5}};
        System.out.println(eraseOverlapIntervals(intervals2)); // Output: 2
    }
}



from typing import List

def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
    # Step 1: Sort intervals by their end times
    intervals.sort(key=lambda x: x[1])

    # Debug: Print sorted intervals
    print("Sorted Intervals:", intervals)

    count = 0  # Initialize the count of intervals to remove
    prev = intervals[0]  # Start with the first interval

    # Step 2: Iterate through the sorted intervals
    for i in range(1, len(intervals)):
        curr = intervals[i]  # Current interval

        # Step 3: Check for overlap
        if prev[1] > curr[0]:
            # Overlap detected, increment the count
            count += 1
        else:
            # No overlap, update previous interval
            prev = curr

    return count


print(eraseOverlapIntervals([[1, 4], [3, 5], [5, 6], [2, 3]]))
print(eraseOverlapIntervals([[2, 3], [2, 3], [2, 3], [4, 5]]))

Output:

Sorted Intervals: [[2, 3], [1, 4], [3, 5], [5, 6]]
1
Sorted Intervals: [[2, 3], [2, 3], [2, 3], [4, 5]]
2

Related Problems: