Data Structures & Algorithms in Java – Intervals – Non overlapping intervals

Problem:

Given an array of intervals , find the minimum number of overlapping intervals that need to be removed so that the array consists of only non overlapping intervals.

For example,

Consider the array of intervals:

[[1,2],[2,3],[3,5],[1,3]]

[1,2] and [1,3] are overlapping.

Also [2,3] and [1,3] are overlapping.

How do you know two intervals are overlapping?

By comparing the end of one interval with the start of another interval.

If the start is less than the end then they overlap.

It means the second interval has started even before the first one ended.

In the above case you can remove [1,3] so that the remaining elements are non overlapping.

Also you can remove [1,2] and [2,3] so that the remaining elements are non overlapping.

Also note that if the end of one interval and the start of another interval are the same , they are considered as non overlapping at least that is the assumption for this problem.

So the minimum number of overlapping intervals to be removed is [1,3] that is 1.

The output is 1.

Try out the solution here:

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

Solution:

• Sort the array and then compare the end of one interval to the start of another interval

Explanation:

We will look at two solutions:

Approach 1: Sort based on the start time of the intervals

For the first one we will sort the array based on the start intervals.

So after sorting the intervals will be in ascending order.

The interval which starts first will be at the beginning, the one which starts next will be next and so on.

So in the above example the sorted array becomes:

[[1,2],[1,3],[2,3],[3,5]]

The second step is as you iterate through the sorted array whenever you see an overlapped interval , remove the one with the highest end . This is because there is more chance of an interval with a higher end to overlap with the next interval than the one with the lesser end. This is because of the gap between the two ends. Some other interval could start from this gap.

So in the above case when we consider the first two intervals [1,2] and [1,3] they overlap since the start of the second interval is less than the end of the previous interval.

We remove the second interval [1,3].

Now the array becomes [[1,2],[2,3],[3,5]] .

We carry on the iteration and see that no other intervals overlap.

So the minimum number of intervals to be removed is 1.

Here is the algorithm:

ALGORITHM:

STEP 1: Sort the array based on the start time of the intervals

STEP 2: Initialize a counter variable to store the result

STEP 3: Find the end of the first interval and store it in a variable say “previous”. This will be compared with the start of the next interval to find it if it overlaps.

STEP 4: Iterate through the rest of the array starting from second element

STEP 4a: For each interval , compare it with the previous interval, if they overlap ignore the interval with the highest end time , point the variable previous to the smallest end interval.

STEP 4b: Increment the counter which keeps track of overlapping intervals to be removed

STEP 4c: If the intervals don’t overlap then don’t increment the counter , just make the previous variable to point to the current interval end.

STEP 5: Return the value of count.

Code:

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        
        
        Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));
        
        int prev = intervals[0][1];
        
        int count = 0;
        
        for(int i=1 ; i < intervals.length;i++){
            
            
            if(intervals[i][0] >= prev){
                
                prev = intervals[i][1];
            }else{
                
                count++;
                
                prev = Math.min(intervals[i][1],prev);
            }
        }
        
        return count;
        
    }
}

Time complexity : O(nlogn) including the sorting and the single pass through the array

Space complexity : O(1) to store the result

Approach 2: Sorting based on end time of intervals.

The solution to the problem :

Minimum number of overlapping intervals to be removed

is the closely related to the solution to the problem:

Maximum number of non overlapping intervals

If you find the maximum number of non overlapping intervals then the difference between the total intervals and this maximum number gives the minimum number of overlapping intervals to be removed.

So we can find the maximum number of non overlapping intervals and subtract this value from the array length.

For this ,

Sort the arrays in ascending order based on the interval end time.

So the above example becomes:

[[1,2],[2,3],[1,3],[3,5]]

Then the second step is to count the intervals whose starting is greater than the ending of the previous intervals (you ignore the ones which overlap)

In the above case if we consider first two intervals [1,2] and [2,3] they are not overlapping so count them .

Then if you consider the next one [1,3] it overlaps so we ignore it.

Then if you consider the next one [3,5] it doesn’t overlap with the last interval considered [2,3] so include it in the count.

The total count is 3.

The array length is 4.

So minimum number of overlapping intervals to be removed = array length – maximum number of non overlapping intervals

= 4 – 3 = 1

So output is 1.

ALGORITHM:

STEP 1: Sort the array in ascending order of end time of intervals

STEP 2: Initialize a counter to store maximum number of non overlapping intervals

STEP 3: Initialize a variable “previous” to point to the end interval time of the first interval

STEP 4: Iterate through the array from the second interval :

STEP 4a: Compare the start of the current interval to the end of the previous interval

STEP 4b: If they dont overlap then increment the count of non overlapping intervals, also point the previous end interval time to the end time of the current interval

STEP 4c: If the intervals overlap ignore the current interval.

STEP 5: Find the difference of the array length and the maximum number of non overlapping intervals and return it.

Code:

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        
        
        Arrays.sort(intervals,(a,b) -> Integer.compare(a[1],b[1]));
        
        int prev = intervals[0][1];
        
        int count = 1;
    
        for(int i=1 ; i < intervals.length;i++){
            
            
            if(intervals[i][0] >= prev){
                
                count++;
                
                prev = intervals[i][1];
            }
        }
        
        return intervals.length - count;
        
    }
}

Time complexity : O(nlogn) for the sorting and the single pass through the array

Space complexity : O(1) since there is no space required in proportion to the input.

That’s it!