Codeforces Div3 #690 Prob-F

PROBLEM STATEMENT LINK:

QUESTION EXPLAINATION:

We have to find a good Set in which anyone segment intersects with a maximum number of segments. We have to delete some segments in order to make it a good set.

For example: [[1,4],[2,3],[3,6]] is a good set, because [2,3] intersects each segment from the set.

[[1,2],[2,3],[3,5],[4,5]] is not a good set, because there is not even any single segment which is intersecting with all other segments. So, we can delete some segments, in order to make it a good set.

Let’s say, we can remove [4,5] and it will become a good set.

Hence, we have to find the minimum number of segments that we have to remove(including 0) in order to make it a good Set.

APPROACH/ALGORITHM:

  1. Store all the range in an array of type pair<int, int> arr[]
  2. Store Left ranges in Left[] i.e., for ex, [1,3], [2,5],[ 5,6], then store only 1,2 and 6.
  3. Store Right ranges in Right[] = {3,5,6}.
  4. Sort the left and right array.
  5. Iterate on the arr[], from 0 till n. Find all the elements in Right[] that are lower than arr[i].left and all the elements in Left[] that are greater than arr[i].right , store it in a variable = counter(let’s say)
  6. ans = min(ans, counter)

Here, what we are doing is, we are finding all the elements that end before the left and all the elements starting after the right, Hence we have to remove these elements in order to make it a good set.

Code Link:

https://codeforces.com/contest/1462/submission/101420915

Happy Coding :)

The girl who loves to code | Software Developer | Follow me at: https://salonix.netlify.app