Solution For Non Overlapping Intervals

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.

Example:
Input: [[1,2],[2,3],[3,4],[1,3]] Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Solution:
This problem can be solved using the concept of Greedy Algorithm. The approach is to sort the intervals based on their end time. We need to start with the interval with the smallest end time as it will give us more space to accommodate other intervals. Whenever we find overlapping intervals, we keep the interval with the smallest end time and remove the other one.

1. Sort the intervals based on their end time.
2. Initialize a variable end with the value of negative infinity. This variable will keep track of the end time of the last included interval.
3. Iterate through all intervals.
4. Check if the start time of the current interval is greater than or equal to end. If yes, include the interval and update the value of end with its end time.
5. Else, discard the current interval.
6. Return the number of intervals that were removed (total number of intervals – number of intervals included in step 4).

Code:

“`
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0

    intervals.sort(key=lambda x: x[1])
    end = float('-inf')
    count = 0

    for interval in intervals:
        start = interval[0]
        if start >= end:
            end = interval[1]
        else:
            count += 1

    return count

“`

Time Complexity: Sorting takes O(nlogn) time and iterating through the intervals takes O(n) time. Thus, the total time complexity is O(nlogn).

Space Complexity: O(1) as we are not using any extra data structure.

Step by Step Implementation For Non Overlapping Intervals

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public int eraseOverlapIntervals(Interval[] intervals) {
        if(intervals == null || intervals.length == 0)
            return 0;
 
        Arrays.sort(intervals, new Comparator(){
            public int compare(Interval i1, Interval i2){
                if(i1.start != i2.start)
                    return i1.start - i2.start;
                else
                    return i1.end - i2.end;
            }
        });
 
        int count = 0;
        int end = intervals[0].end;
        for(int i=1; i

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

# Input: [ [1,2], [2,3], [3,4], [1,3] ]
# Output: 1
# Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

# Input: [ [1,2], [1,2], [1,2] ]
# Output: 2
# Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

# Input: [ [1,2], [2,3] ]
# Output: 0
# Explanation: Intervals [1,2] and [2,3] are already non-overlapping.

def eraseOverlapIntervals(intervals):
    
    # sort the intervals by their start time
    intervals.sort(key=lambda x: x[0])
    
    # keep track of the number of intervals we need to remove
    count = 0
    
    # start with the interval with the earliest start time
    i = 0
    
    # compare this interval with the next interval in the list
    while i < len(intervals) - 1:
        # if the current interval overlaps with the next interval,
        if intervals[i][1] > intervals[i+1][0]:
            # remove the interval with the later end time
            if intervals[i][1] > intervals[i+1][1]:
                i += 1
            # if the end times are the same, remove the interval with the later start time
            else:
                i += 2
            # increment our counter
            count += 1
        # if the current interval does not overlap with the next interval, move on to the next interval
        else:
            i += 1
    
    return count
/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
    // sort the intervals by start time
    intervals.sort((a, b) => a[0] - b[0]);
    
    // keep track of the number of non-overlapping intervals
    let count = 0;
    
    // keep track of the end time of the previous interval
    let end = 0;
    
    // iterate through the intervals
    for (let interval of intervals) {
        // if the current interval starts before the end of the previous interval,
        // then they must be overlapping
        if (interval[0] < end) {
            // if the current interval's end time is less than the previous interval's end time,
            // then we can remove the current interval since it is completely contained within
            // the previous interval
            if (interval[1] < end) {
                count++;
            }
        } else {
            // otherwise, the current interval is non-overlapping, so we can update the end time
            // to be the current interval's end time
            end = interval[1];
        }
    }
    
    return count;
};
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 can "touch", such as [0, 1] and [1, 2], but they won't be considered overlapping.

For example, given the intervals (7, 9), (2, 4), (5, 8), return 1 as the last interval can be removed and the first two won't overlap.

The intervals are not necessarily sorted in any order.

Solution:

#include 
#include 
#include 

using namespace std;

class Solution {
public:
    int eraseOverlapIntervals(vector>& intervals) {
        if (intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end(), [](vector& a, vector& b){
            return a[1] < b[1];
        });
        int count = 0;
        int end = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < end) count++;
            else end = intervals[i][1];
        }
        return count;
    }
};
/**
 * Definition for an interval.
 * public class Interval {
 *     public int start;
 *     public int end;
 *     public Interval() { start = 0; end = 0; }
 *     public Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public int EraseOverlapIntervals(Interval[] intervals) {
        // sort the intervals by start time
        Array.Sort(intervals, (a, b) => a.start.CompareTo(b.start));
        
        // keep track of the end time of the previous interval
        int end = int.MinValue;
        int count = 0;
        
        // for each interval
        foreach(var interval in intervals) {
            // if the current interval overlaps with the previous interval
            if(interval.start < end) {
                // we can delete either interval, so increment the delete count
                count++;
                
                // and delete the interval with the larger end time
                if(interval.end < end) {
                    end = interval.end;
                }
            } else {
                // otherwise update the end time of the previous interval
                end = interval.end;
            }
        }
        
        return count;
    }
}