# 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.

- Sort the intervals based on their end time.
- Initialize a variable
`end`

with the value of negative infinity. This variable will keep track of the end time of the last included interval. - Iterate through all intervals.
- 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. - Else, discard the current interval.
- 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; } }