Maximum circles

#1

Here’s my code for maximum circles using greedy approach. I am getting correct output for sample case but it fails when I submit on hackerblocks. Can you tell me where I am going wrong?
Ps:- no need in correction of code, I just want to know where I am wrong in my thinking.

#2

Hey @div_yanshu07
Please explain ur logic in brief.
Dont tell me what u did like u ran a loop this times etc.

Give me ur logic in simple English and I will tell u where u are going wrong.

Btw this is variation of activity selection problem .

#3

So, what I am trying is that I am picking first circle(i.e res=1). Then I am calculating the coordinates that it has covered and storing it in distance so for eg in first case center as 1 and radius as 1 it covers 2*1(v[0].second)=2 coordinate. Now any circle will not be considered as overlapped if its ahead of 2. Now, inside loop in K I am calculating the second circles radius so 2-1=1 and 1 is not greater or equal than 2 , so, I skip this circle. Now I have 3 as a center and 1 as a radius now 3-1= 2which is greater than =2. So, this circle can be picked, now I am updating my distance as 3+1=4. So that next circle’s coordinate should be greater than =4.

I hope I made myself clear example discussed is from sample test case

#4

Consider Centre is 3 and radius is 1 so still u are considering it covers 2 though it covers 2 to 4, so every circle which comes after 4 should be taken also
assume
first circle as 1 10 and rest as 2 1, 3 1 , 4 1
So in this case we leave the first one and take the rest .
See here also ur logic doesn’t work

Correct logic
this problem is a variation of activity selection problem.
for each circle store left and right end of the circle in an array and then apply logic similar to activity selection to find maximum number of non overlapping circles.
let say answer u get from above logic is ans.
print n-ans as ur answer because question asked minimum circle we remove to make other circles non overlapping.

#5

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.