# 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

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;
}
}```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]