# Minimize segments required to be removed such that at least one segment intersects with all remaining segments

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

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:arr[] = {{1, 2}, {5, 6}, {6, 7}, {7, 10}, {8, 9}}Output:2Explanation: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:0Explanation: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 **[f _{1}, s_{1}] **and

**[f**intersect only when

_{2}, s_{2}]**max(f**.

_{1}, f_{2}) â‰¤ min(s_{1}, s_{2})Therefore, if

**[f**does not intersect with

_{1}, s_{1}]**[f**, then there are only two possibilities:

_{2}, s_{2}]**s**_{1 }< f_{2}_{ }i.e segment 1 ends before the start of segment 2**f**i.e segment 1 starts after the end of segment 2._{1 }> s_{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**.

- Store the number of segments satisfying the first and the second condition of non-intersection in
- 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 deleted` `void` `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 Code` `int` `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 approach` `import` `java.io.*;` `import` `java.lang.*;` `import` `java.util.*;` `class` `GFG{` `// Pair class` `static` `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 deleted` `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` ` ` `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 Code` `public` `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

`# Pyhton3 program for the above approach` `from` `bisect ` `import` `bisect_left,bisect_right` `# Function to find the minimum number` `# of segments required to be deleted` `def` `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 Code` `if` `__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.` |

**Output:**

2

**Time Complexity:** O(N*(log N^{2}))**Auxiliary Space:** O(N)