Algorithm/DS Problem#3: Minimum non-overlapping bridges

You are given n coordinates[north, south] of N bridges
Count of maximum number of non-overlapping bridges.

Ex: [[6,2],[4,3],[2,6],[1,5]]    6 4 2 1 North
2 3 6 5 South
B1 B2 B3 B4
Output: 2
For non-overlapping bridges, the following is TRUE:
north1 < north2 and South1 < South2
1 < 2 and 2 < 6
Idea here is to do the below:
(a) Sort all bridges based on north bank
(b) Find the LIS(Longest Increasing Subsequence) for each bridge based on south bank

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
svalak

svalak

Passionate about problem solving; #WritesOnQuora #VoraciousReader #MBTIEnthusiast #LovePsychology https://www.quora.com/profile/Shaila-Hegde-2