2

I've something that bothers me. I'm trying to solve building bridge problem which have this information as a instruction.

Building Bridges
Consider a 2-D map with a horizontal river passing through its center. There are n cities on the southern bank with x-coordinates a(1) ... a(n) and n cities on the northern bank with x-coordinates b(1) ... b(n).
You want to connect as many north-south pairs of cities as possible with bridges such that no two bridges cross. When connecting cities, you can only connect city i on the northern bank to city i on the southern bank."

I did research on Stack Overflow and found out some topic that really help me a lot such as:
Building bridges problem - how to apply longest increasing subsequence? and
How to determine the longest increasing subsequence using dynamic programming?

But when I come up with LIS and trying to solve one sample list by hand. Let's say I have

Northern Bank >> 7 4 3 6 2 1 5
Southern Bank >> 5 3 2 4 6 1 7

After sort southern bank 

Northern Bank >> 1 3 4 6 7 2 5 
Southern Bank >> 1 2 3 4 5 6 7

Which LIS length suppose to be "5" but actually in the first list, Only 3 bridge are able to create (3,2,1). So did I misunderstand LIS or are there any exception on this that won't work on building bridge problem?

Community
  • 1
  • 1
user2898386
  • 23
  • 1
  • 3

1 Answers1

4

My understanding is that you have correctly solved the problem using the longest increasing subsequence:

enter image description here

You can build all 5 black bridges (but not the 2 red ones).

Why do you think you can only make 3 bridges?

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
  • the instruction said that you can only connect city i on the northern bank to city i on the southern bank." So I though that we've to connect to the same number on both side. Am I misunderstand the instruction cause if not, when I recheck back to original sequence Northern Bank >> 7 4 3 6 2 1 5 Southern Bank >> 5 3 2 4 6 1 7 I can connect only 3, 2,1 or 3,6,1 or 4,6,1 only – user2898386 Oct 20 '13 at 01:46
  • 1
    The original sequence is saying that north city 1 at x 7.0 can only connect to south city 1 at x 5.0, north city 2 at a 4.0 can only connect to south city 2 at x 3.0, etc. In other words, the original sequence specifies the locations of 7 possible bridges - the ones shown in my diagram. Note the numbers in my diagram are x positions. The city indices are not shown. – Peter de Rivaz Oct 20 '13 at 08:14
  • thank you Peter de Rivaz. I got it now. Your answer really help me a lot. – user2898386 Oct 21 '13 at 16:31