Given an array arr[] consisting of N pairs [L, R], where L and R denotes the start and end indices of a segment, the task is to find the minimum number of segments that must be deleted from the array such that the remaining array contains at least one segment which intersects with all other segments present in the array.
Examples:
Input: arr[] = {{1, 2}, {5, 6}, {6, 7}, {7, 10}, {8, 9}}
Output: 2
Explanation: Delete the segments {1, 2} and {5, 6}. Therefore, the remaining array contains the segment {7, 10} which intersects with all other segments.Input: a[] = {{1, 2}, {2, 3}, {1, 5}, {4, 5}}
Output: 0
Explanation: The segment {1, 5} already intersects with all other remaining segments. Hence, no need to delete any segment.
Approach: The maximum possible answer is (N – 1), since after deleting (N – 1) segments from arr[], only one segment will be left. This segment intersects with itself. To achieve the minimum answer, the idea is to iterate through all the segments, and for each segment, check the number of segments which do not intersect with it.
Two segments [f1, s1] and [f2, s2] intersect only when max(f1, f2) ? min(s1, s2).
Therefore, if [f1, s1] does not intersect with [f2, s2], then there are only two possibilities:
- s1 < f2 i.e segment 1 ends before the start of segment 2
- f1 > s2 i.e segment 1 starts after the end of segment 2.
Follow the steps below to solve the problem:
- Traverse the array arr[] and store the starting point and ending point of each segment in startPoints[], and endPoints[] respectively.
- Sort both the arrays, startPoints[] and endPoints[] in increasing order.
- Initialize ans as (N – 1) to store the number of minimum deletions required.
- Again traverse the array, arr[] and for each segment:
- Store the number of segments satisfying the first and the second condition of non-intersection in leftDelete and rightDelete respectively.
- If leftDelete + rightDelete is less than ans, then set ans to leftDelete + rightDelete.
- After the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum number// of segments required to be deletedvoid minSegments(pair<int, int> segments[], int n){ // Stores the start and end points int startPoints[n], endPoints[n]; // Traverse segments and fill the // startPoints and endPoints for (int i = 0; i < n; i++) { startPoints[i] = segments[i].first; endPoints[i] = segments[i].second; } // Sort the startPoints sort(startPoints, startPoints + n); // Sort the startPoints sort(endPoints, endPoints + n); // Store the minimum number of // deletions required and // initialize with (N - 1) int ans = n - 1; // Traverse the array segments[] for (int i = 0; i < n; i++) { // Store the starting point int f = segments[i].first; // Store the ending point int s = segments[i].second; // Store the number of segments // satisfying the first condition // of non-intersection int leftDelete = lower_bound(endPoints, endPoints + n, f) - endPoints; // Store the number of segments // satisfying the second condition // of non-intersection int rightDelete = max( 0, n - (int)(upper_bound(startPoints, startPoints + n, s) - startPoints)); // Update answer ans = min(ans, leftDelete + rightDelete); } // Print the answer cout << ans;}// Driver Codeint main(){ pair<int, int> arr[] = { { 1, 2 }, { 5, 6 }, { 6, 7 }, { 7, 10 }, { 8, 9 } }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call minSegments(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Pair classstatic class Pair { int first; int second; Pair(int first, int second) { this.first = first; this.second = second; }}public static int lower_bound(int arr[], int key){ int l = -1, r = arr.length; while (l + 1 < r) { int m = (l + r) >>> 1; if (arr[m] >= key) r = m; else l = m; } return r;}public static int upper_bound(int arr[], int key){ int l = -1, r = arr.length; while (l + 1 < r) { int m = (l + r) >>> 1; if (arr[m] <= key) l = m; else r = m; } return l + 1;}// Function to find the minimum number// of segments required to be deletedstatic void minSegments(Pair segments[], int n){ // Stores the start and end points int startPoints[] = new int[n]; int endPoints[] = new int[n]; // Traverse segments and fill the // startPoints and endPoints for(int i = 0; i < n; i++) { startPoints[i] = segments[i].first; endPoints[i] = segments[i].second; } // Sort the startPoints Arrays.sort(startPoints); // Sort the startPoints Arrays.sort(endPoints); // Store the minimum number of // deletions required and // initialize with (N - 1) int ans = n - 1; // Traverse the array segments[] for(int i = 0; i < n; i++) { // Store the starting point int f = segments[i].first; // Store the ending point int s = segments[i].second; // Store the number of segments // satisfying the first condition // of non-intersection int leftDelete = lower_bound(endPoints, f); // Store the number of segments // satisfying the second condition // of non-intersection int rightDelete = Math.max( 0, n - (int)(upper_bound(startPoints, s))); // Update answer ans = Math.min(ans, leftDelete + rightDelete); } // Print the answer System.out.println(ans);}// Driver Codepublic static void main(String[] args){ Pair arr[] = { new Pair(1, 2), new Pair(5, 6), new Pair(6, 7), new Pair(7, 10), new Pair(8, 9) }; int N = arr.length; // Function Call minSegments(arr, N);}}// This code is contributed by Kingash |
Python3
# Python3 program for the above approachfrom bisect import bisect_left,bisect_right# Function to find the minimum number# of segments required to be deleteddef minSegments(segments, n): # Stores the start and end points startPoints = [0 for i in range(n)] endPoints = [0 for i in range(n)] # Traverse segments and fill the # startPoints and endPoints for i in range(n): startPoints[i] = segments[i][0] endPoints[i] = segments[i][1] # Sort the startPoints startPoints.sort(reverse = False) # Sort the startPoints endPoints.sort(reverse= False) # Store the minimum number of # deletions required and # initialize with (N - 1) ans = n - 1 # Traverse the array segments[] for i in range(n): # Store the starting point f = segments[i][0] # Store the ending point s = segments[i][1] # Store the number of segments # satisfying the first condition # of non-intersection leftDelete = bisect_left(endPoints, f) # Store the number of segments # satisfying the second condition # of non-intersection rightDelete = max(0, n - bisect_right(startPoints,s)) # Update answer ans = min(ans, leftDelete + rightDelete) # Print the answer print(ans)# Driver Codeif __name__ == '__main__': arr = [[1, 2],[5, 6], [6, 7],[7, 10],[8, 9]] N = len(arr) # Function Call minSegments(arr, N) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG { // Pair class class Pair { public int first; public int second; public Pair(int first, int second) { this.first = first; this.second = second; } } public static int lower_bound(int[] arr, int key) { int l = -1, r = arr.Length; while (l + 1 < r) { int m = (l + r) >> 1; if (arr[m] >= key) r = m; else l = m; } return r; } public static int upper_bound(int[] arr, int key) { int l = -1, r = arr.Length; while (l + 1 < r) { int m = (l + r) >> 1; if (arr[m] <= key) l = m; else r = m; } return l + 1; } static void minSegments(Pair[] segments, int n) { // Stores the start and end points int[] startPoints = new int[n]; int[] endPoints = new int[n]; // Traverse segments and fill the // startPoints and endPoints for (int i = 0; i < n; i++) { startPoints[i] = segments[i].first; endPoints[i] = segments[i].second; } // Sort the startPoints Array.Sort(startPoints); // Sort the startPoints Array.Sort(endPoints); // Store the minimum number of // deletions required and // initialize with (N - 1) int ans = n - 1; // Traverse the array segments[] for (int i = 0; i < n; i++) { // Store the starting point int f = segments[i].first; // Store the ending point int s = segments[i].second; // Store the number of segments // satisfying the first condition // of non-intersection int leftDelete = lower_bound(endPoints, f); // Store the number of segments // satisfying the second condition // of non-intersection int rightDelete = Math.Max( 0, n - (int)(upper_bound(startPoints, s))); // Update answer ans = Math.Min(ans, leftDelete + rightDelete); } // Print the answer Console.WriteLine(ans); } static public void Main() { // Code Pair[] arr = { new Pair(1, 2), new Pair(5, 6), new Pair(6, 7), new Pair(7, 10), new Pair(8, 9) }; int N = arr.Length; minSegments(arr, N); }}// This code is contributed by lokesh (lokeshmvs21). |
Javascript
// JS program for the above approachfunction lowerBound(arr, key) { let l = -1, r = arr.length; while (l + 1 < r) { let m = (l + r) >>> 1; if (arr[m] >= key) r = m; else l = m; } return r;}function upperBound(arr, key) { let l = -1, r = arr.length; while (l + 1 < r) { let m = (l + r) >>> 1; if (arr[m] <= key) l = m; else r = m; } return l + 1;}// Function to find the minimum number// of segments required to be deletedfunction minSegments(segments, n) { // Stores the start and end points let startPoints = []; let endPoints = []; // Traverse segments and fill the // startPoints and endPoints for (let i = 0; i < n; i++) { startPoints.push(segments[i].first); endPoints.push(segments[i].second); } // Sort the startPoints startPoints.sort(); // Sort the startPoints endPoints.sort(function (a, b) { return a - b }); // Store the minimum number of // deletions required and // initialize with (N - 1) let ans = n - 1; // Traverse the array segments[] for (let i = 0; i < n; i++) { // Store the starting point let f = segments[i].first; // Store the ending point let s = segments[i].second; // Store the number of segments // satisfying the first condition // of non-intersection let leftDelete = lowerBound(endPoints, f); // Store the number of segments // satisfying the second condition // of non-intersection let rightDelete = Math.max(0, n - Math.floor(upperBound(startPoints, s))); // Update answer ans = Math.min(ans, leftDelete + rightDelete); } // Print the answer console.log(ans);}// Driver Codearr = [{ "first": 1, "second": 2 },{ "first": 5, "second": 6 },{ "first": 6, "second": 7 },{ "first": 7, "second": 10 },{ "first": 8, "second": 9 }];let N = arr.length;// Function CallminSegments(arr, N);// This code is contributed by akashish__. |
Output:
2
Time Complexity: O(N*(log N2))
Auxiliary Space: O(N)
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!
