Be the first user to complete this post

  • 0
 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 [3, 5] 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:

 
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: