Algorithm/DS Problem#3: Minimum 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 learning ; Will write about #systemdesign #DSA #algorithms #linuxinternals #technology; Painting/Poem writing are my hobbies; Voracious Reader