Greedy on graph

#1

This approach seems to me like a greedy algo on graph. Am I correct? So we can maintain an array and use two pointers based approach as well. Can we?

Thanks.

#2

hello @begginner_cp
yeah the approach is greedy.

how?

#3

So we can sort the array in ascending order then maintain two pointers like in case of multiset low and high and the remaining is similar

#4

try it and see if its working or not

#5

Ok I’ll try, thanks.

#6

Basically what I’m telling is that instead of multiset we will keep an array. So what is the purpose of multiset is that to have the numbers in sorted order, so we can have the same numbers in array and explicitly sort the.

I suppose the the only advantage of multiset is time complexity of removing elements that can be done in logN time

#7

yeah that will work…

u need to explicitly sort ur trans array , after that u can keep two pointers

1 Like
#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.