Bridges(DP challenges)

#1

I am not able to understand the sample test case.

#2

Hello @sahilraja242

Test Case
1
4
2 5 8 10
6 4 1 2

Here we have 4 endpoints mentioned above.
So according to the question there can be bridges between (2, 6), (5, 4), (8, 1), (10, 2)
Now plot these points on a X-Y co-ordinate system and join the end-points.
You will see that the bridges
(2, 6), (5, 4) intersect
(2, 6), (8, 1) intersect
(2, 6), (10, 2) intersect
(5, 4), (8, 1) intersect
(5, 4), (10, 2) intersect

Now we need to build maximum number of bridges keeping in mind that they do not intersect
So if you build all the bridges, there will be intersections as seen above.
If you build the first three bridges only there still would be intersections
But if you build the last two only, there would be No intersections and this is the set containing Non-intersecting bridges and is the largest in size.
ans 2

Let me know if you still need any help.

#3

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.