Non-overlapping Intervals

bool order_by_second(vector<int>& vec1, vector<int>& vec2) {
    return vec1[1] < vec2[1];
}
    
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), order_by_second);
        int count = 0;
        int last_end = INT_MIN;
            
        for (int i = 0; i < intervals.size(); i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];
                
            if (start >= last_end) {
                last_end = end;
            } else {
                count++;
            }
        }
            
        return count;
    }
};

The provided C++ code offers a solution for finding the minimum number of intervals you need to remove from a set to ensure that no two intervals overlap. Here's a step-by-step explanation of what the code does:

• The order_by_second function defines a custom comparator to sort intervals based on their endpoint values. It ensures that the vector of intervals will be sorted in ascending order by the second element of each sub-vector.

• Within the Solution class:

  • The eraseOverlapIntervals function is defined to take a two-dimensional vector of integers, where each sub-vector represents an interval with a start and end point.

  • The intervals are first sorted by their end times using the sort() function and the custom comparator order_by_second.

  • Initialization is done for count which will keep a tally of the number of intervals that need to be removed, and last_end which tracks the end point of the last added interval, starting from the smallest possible integer.

  • A loop iterates through each interval:

    • The start and end of the current interval are determined.
    • A check is performed to see if the current interval's start time is not less than the last_end. If true, last_end is updated to the current interval's end time. Otherwise, it indicates an overlap, and the count is incremented.

  • After completing the loop through all intervals, the function returns the count of intervals that need to be removed.

This approach ensures an efficient determination of the minimum number of intervals to be removed for non-overlapping, employing sorting and a greedy algorithm strategy. The correctness is ensured as intervals are managed based on the least end time to maximize the chance of no overlap with forthcoming intervals.

class Solution {
    public int removeOverlappingIntervals(int[][] data) {
        Arrays.sort(data, Comparator.comparingInt(a -> a[1]));
        int removed = 0;
        int lastEnd = Integer.MIN_VALUE;
            
        for (int i = 0; i < data.length; i++) {
            int start = data[i][0];
            int end = data[i][1];
                
            if (start >= lastEnd) {
                lastEnd = end;
            } else {
                removed++;
            }
        }
            
        return removed;
    }
}

The Java solution provided addresses the problem of finding the minimum number of intervals you need to remove to make the rest non-overlapping. It devices a strategic method by first sorting the intervals based on their end times, and then iterating through the sorted list to determine the necessity of removing an interval.

• First, sort the array of intervals data based on the endpoint of each interval. This ensures that you always have the smallest possible 'end' to compare with, optimizing the chances of the subsequent interval not overlapping.

• Initialize an integer removed to count the number of intervals that need removal to prevent overlap.

• Initialize lastEnd to the smallest possible integer value. This variable keeps track of the endpoint of the last added interval that did not overlap.

• Iterate over each interval:

  • Extract the start and end of the current interval.
  • If the start of the current interval is greater than or equal to lastEnd, update lastEnd to this interval’s end since this interval does not overlap with the previously stored interval.
  • If the start is less than lastEnd, increment the removed counter as this interval overlaps with the previous one and needs to be removed.

• Return the removed count which represents the minimum number of intervals to eliminate to ensure that none of the remaining intervals overlap.

By efficiently selecting only those intervals that finish the earliest and do not overlap, this solution minimizes the deletions necessary to achieve non-overlapping intervals.

class Solution:
    def removeOverlapping(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda interval: interval[1])
        removed = 0
        last_end = float('-inf')
            
        for start, end in intervals:
            if start >= last_end:
                last_end = end
            else:
                removed += 1
            
        return removed

In this Python solution, the goal is to determine the minimum number of intervals you need to remove to ensure that no intervals overlap.

Here's a step-by-step review of how the solution works:

1. Sort the intervals list based on the endpoint of each interval using a lambda function. This helps in selecting the intervals that finish the earliest, allowing more room for subsequent intervals to be included without overlapping.

2. Initialize removed to 0, which will keep track of the count of intervals that need to be removed to avoid overlap.

3. Initialize last_end to negative infinity. This variable tracks the end of the last interval that was added without overlapping.

4. Iterate through each interval. For each start and end:

   • If start is greater than or equal to last_end, update last_end to the current end. This means the current interval does not overlap with the previously considered interval.
   • If start is less than last_end, increment the removed counter by 1 because the current interval overlaps with the previous interval and must be removed to avoid overlap.

5. Return the removed count, which is the number of intervals removed to achieve the necessary non-overlapping condition.

By adhering to this approach, the solution efficiently calculates the minimum number of deletions required to ensure that no two intervals overlap, using sorting and a simple iteration through the list.