Minimum removals required to make ranges non-overlapping

0 0 4 minutes read

Given a list of ranges with starting and end value, the task is to find the minimum number of ranges that are required to be removed to make remaining ranges non-overlapping. Examples:

Input : input = {{1, 2}, {4, 7}, {3, 8}} Output : 1 Explanation: Removal of {3, 8} makes {{1, 2} and {4, 7}} non-overlapping. Input : input = {{ 10, 20 }, { 10, 20 } , { 10, 20 }} Output : 2 Explanation: Removal of [10, 20] makes the remaining ranges non-overlapping. Input : input = {{1, 2}, {5, 10}, {18, 35}, {40, 45}} Output : 0 Explanation:All ranges are already non-overlapping.

Approach:

Sort the ranges by their starting values.
Traverse through the ranges and check if any range has a starting point less than the ending point of the previous (ie. there is an overlap).
Remove the range with greater ending point.

Below code is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
int minRemovals(vector<vector<int> >& ranges)
{
 
    int size = ranges.size(), rem = 0;
 
    if (size <= 1)
        return 0;
 
    // Sort by minimum starting point
    sort(ranges.begin(), ranges.end(),
        [](const vector<int>& a, const vector<int>& b)
                    { return a[0] < b[0]; });
 
    int end = ranges[0][1];
    for (int i = 1; i < ranges.size(); i++) {
 
        // If the current starting point is less than
        // the previous interval's ending point
        // (ie. there is an overlap)
        if (ranges[i][0] < end) {
            // increase rem
            rem++;
            // Remove the interval
            // with the higher ending point
            end = min(ranges[i][1], end);
        }
        else
            end = ranges[i][1];
    }
 
    return rem;
}
 
// Driver code
int main()
{
    vector<vector<int> > input = { { 19, 25 },
                        { 10, 20 }, { 16, 20 } };
    cout << minRemovals(input) << endl;
}

Java

//Java equivalent of above code
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
 
public class Main {
  public static int minRemovals(List<int[]> ranges) {
    int size = ranges.size(), rem = 0;
 
    if (size <= 1)
      return 0;
 
    // Sort by minimum starting point
    Collections.sort(ranges, new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        return o1[0] - o2[0];
      }
    });
 
    int end = ranges.get(0)[1];
    for (int i = 1; i < ranges.size(); i++) {
      // If the current starting point is less than
      // the previous interval's ending point
      // (ie. there is an overlap)
      if (ranges.get(i)[0] < end) {
        // increase rem
        rem++;
        // Remove the interval
        // with the higher ending point
        end = Math.min(ranges.get(i)[1], end);
      } else
        end = ranges.get(i)[1];
    }
 
    return rem;
  }
 
  // Driver code
  public static void main(String[] args) {
    List<int[]> input = new ArrayList<int[]>();
    input.add(new int[] { 19, 25 });
    input.add(new int[] { 10, 20 });
    input.add(new int[] { 16, 20 });
    System.out.println(minRemovals(input));
  }
}

Python3

def minRemovels (ranges):
 
    size = len(ranges)
    rem = 0
 
    # Sort by minimum starting point
    ranges.sort()
 
    end = ranges[0][1]
    for i in range(1, size):
 
        # If the current starting point is less
        # than the previous interval's ending
        # point (ie. there is an overlap)
        if (ranges[i][0] < end):
 
            # Increase rem
            rem += 1
 
            # Remove the interval
            # with the higher ending point
            end = min(ranges[i][1], end)
             
        else:
            end = ranges[i][1]
 
    return rem
 
# Driver Code
if __name__ == '__main__':
     
    Input = [ [ 19, 25 ],
            [ 10, 20 ],
            [ 16, 20 ] ]
                 
    print(minRemovels(Input))
 
# This code is contributed by himanshu77

C#

using System;
using System.Linq;
 
class GFG {
  static int MinRemovals(int[][] ranges)
  {
    int size = ranges.Length;
    int rem = 0;
 
    // Sort by minimum starting point
    Array.Sort(ranges, (a, b) => a[0] - b[0]);
 
    int end = ranges[0][1];
    for (int i = 1; i < size; i++)
    {
       
      // If the current starting point is less than
      // the previous interval's ending point (ie.
      // there is an overlap)
      if (ranges[i][0] < end) 
      {
         
        // Increase rem
        rem += 1;
 
        // Remove the interval with the higher
        // ending point
        end = Math.Min(ranges[i][1], end);
      }
      else {
        end = ranges[i][1];
      }
    }
 
    return rem;
  }
 
  // Driver code
  public static void Main(string[] args)
  {
    int[][] ranges
      = new int[][] { new int[] { 19, 25 },
                     new int[] { 10, 20 },
                     new int[] { 16, 20 } };
 
 
    // Function call
    Console.WriteLine(MinRemovals(ranges));
  }
}
 
// This code is contributed by phasing17

Javascript

// JavaScript implementation to find the minimum
// removals required to make intervals non-overlapping
function minRemovels(ranges) {
    var size = ranges.length;
    var rem = 0;
 
    // Sort by minimum starting point
    ranges.sort(function(a, b) {
        return a[0] - b[0];
    });
     
    var end = ranges[0][1];
    for (var i = 1; i < size; i++) {
        // If the current starting point is less than the previous interval's ending
        // point (ie. there is an overlap)
        if (ranges[i][0] < end) {
            // Increase rem
            rem += 1;
     
            // Remove the interval with the higher ending point
            end = Math.min(ranges[i][1], end);
     
        } else {
            end = ranges[i][1];
        }
    }
     
    return rem;
}
 
// Driver Code
var ranges = [[19, 25], [10, 20], [16, 20]];
console.log(minRemovels(ranges));
 
// This code is contributed by phasing17

Output

Time Complexity: O(n log n)
Auxiliary Space: O(1) as no extra space has been used.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!