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 codeint main(){ vector<vector<int> > input = { { 19, 25 }, { 10, 20 }, { 16, 20 } }; cout << minRemovals(input) << endl;} |
Java
//Java equivalent of above codeimport 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 Codeif __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-overlappingfunction 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 Codevar ranges = [[19, 25], [10, 20], [16, 20]];console.log(minRemovels(ranges));// This code is contributed by phasing17 |
Output
2
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
