Maximum Selections Geeks For Geeks

 Problem Link:

https://practice.geeksforgeeks.org/problems/87ecf96cfd61e511c697c8c94d21c5de7f471fcb/1#

It is also the problem of the day for 06 April 2022

Solution:

class solver

{

    static int max_non_overlapping(int ranges[][], int n){

    Arrays.sort(ranges,(range1,range2)->(range1[1]-range2[1]));

        int count=0;

        int last=Integer.MIN_VALUE;

        for(int i=0;i<ranges.length;i++){

            if(ranges[i][0]>=last){

                count++;

                last=ranges[i][1];

            }

        }

        return count;

    }

}

Time Complexity:O(NlogN)[GFG Time:2.83/4.04]

Space Complexity: O(N)

Auxiliary Space: O(1)

Approach Used:

Here we follow a standard approach:

1. We will sort the second elements first and then arrange the whole array.

eg1: (2,4) and (3,1) are given then we will sort according to the end distance and hence after sorting we will get (3,1) and (2,4)

eg2: (3,8) and (2,8) are given then their second parameter is the same and in the array, we will arrange them according to their order of arrival ie (3,8) and (2,8)

Now we will apply loop and check condition as 

if(start>= vd){

        count++;

        last=vd;

}

where vd means Integer.MIN_VALUE that is (-infinity)

and start is the first parameter in the array

the count is the total number of pairs counted while traversing the whole array which will satisfy the condition of non-overlapping events.

Here we have written eq as start>=vd in which we have used equals to. This is so because in question it mentioned that the ending of the range being the same as of start is not considered an overlap.

In this way, we will traverse the whole array and get the desired result as a count.

 

Total Test Cases:525

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"