Greedy Algorithms

Question 1

(Easy) Non-overlapping Intervals

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 1:

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.

https://leetcode.com/problems/non-overlapping-intervals/

Variation of: Maximal Disjoint Intervals

Given a set of N intervals, the task is to find the maximal set of mutually disjoint intervals. Two intervals [i, j] & [k, l] are said to be disjoint if they do not have any point in common.

Answer 1

Approach:

1. Sort the intervals based on their end points.
2. Now traverse the array and if intervals overlap greedily choose the interval with lower endpoint.
3. Initial size - maximal array size would give us the ans of minimum intervals to remove.

public int eraseOverlapIntervals(int[][] intervals) {
if(intervals.length==0)return 0;
Arrays.sort(intervals, new Comparator< int[]> () {
@Override
public int compare(int[] i1, int[] i2) {
return i1[1]-i2[1];
}
});
int[] prev = intervals[0];
int res=1;

for(int[] interval: intervals){
if(interval==intervals[0]) continue;
if(interval[0] > =prev[1]){
res++; prev=interval;
}
}
return intervals.length-res;
}