Problem Bridges

#1

I could not understand how to approach this problem , i got that we have to do in O(n2) time but maximum number of non-overlapping ranges , how to find it

#2

@aryan_007
in this problem u are given,
n bridges and u need to tell maximum number of non intersecting beidges .
image

for ex-> here we have 4 bridges
(2,6) , (5,4) , (8,1) ,(10,2)
maximum non intersecting bridges are ->2
i,e (8,1) and (10,2) they will not cross each other.

#3

what does cross mean here , as 1 8 lie completely inside 2 10 ?

#4

and is their any difference between 1 8 and 8 1

#5

@aryan_007
see these statements

bridge starting from the ith end point on one side can only end on the ith end point on the other side
2.The tribe just wants to make as many non-cutting bridges as possible, with the constraint in mind.
for 1st test:
4
2 5 8 10
6 4 1 2
ans is 2 because of (1,8) and (2,10)
for explanation refer this image

bridge

So you need to find Longest increasing subsequence in both arrays.
This is an implementation in case you have further doubts https://ide.codingblocks.com/s/280668

1 Like
#6

Thankyou so much for the diagram , it resolved all my doubts

#7

But i am getting only 1 test case passed , why ???

#8

@aryan_007
refer to this corrected code

#9

i find LIS of given array and reverse array , and gave maximum out of them , what’s the fault in this . And please don’t reply so late , try to solve a doubt in 1 day !!

#10

okay figured out , thanks !!