Sunshine is delicious, rain is refreshing, wind braces us up, snow is exhilarating; there is really no such thing as bad weather, only different kinds of good weather.
Maximum Non - Overlapping Bridges
Welcome Back Reader!
In this article we will discuss about the next problem based on "Dynamic Programming" i.e. "Maximum Non - Overlapping Bridges".
Prerequisite of this problem is "Longest Increasing Subsequence" (LIS), because this problem is just an application of that problem. However, this problem is not exactly based on LIS, but yes it can be reduced to LIS for sure. This is quite an interesting problem. Stay tuned.
Before you move any further, it is advised that you give this problem a fair try.
Let's jump to the problem.
In this problem you are given a number n, representing the number of elements of the array. This n is followed by n pairs of numbers, representing the north bank and south bank coordinates of each bridge.
All you are required to do is to print the count of the maximum number of non - overlapping bridges.
10 - 20, 2 - 7, 8 - 15, 21 - 40, 41 - 57, 60 - 80 and 80 - 90 are the maximum number of bridges that are not overlapping each other and therefore making the count 7.
For more clarity of the question, watch this part of the video.
Moving On:
In this problem we need to count the maximum number of non - overlapping bridges.
This can be obtained if we are able to get a subsequence whose both coordinates of the first occurring bridge are smaller than that of the second occurring bridge.
The naive approach to solve this would be to consider all the possible subsequences by making a choice for each bridge, whether to select it or not. We get 2^n different cases using this way.
To get the valid subsequence, we need to check for each subsequence the condition of non overlapping, using a nested loop, which will take time of O(n^2) for each subsequence, making the overall time complexity O((2^n)(n^2)), which is not at all a smart way to solve this.
So, we now move to the second approach. We start solving this problem by sorting the given bridges on the basis of the north bank's coordinates.
After that we apply the longest increasing subsequence algorithm on this sorted array but this time we make use of the south bank's coordinates to do so.
Let's try to apply above points to the sample input array:
So first of all we sort the bridges on the basis of north bank coordinates.
After that we apply the steps of Longest Increasing Subsequence (LIS) to the south bank coordinates of the bridges.
On applying the LIS on the south bank's coordinates, we get the longest subsequence which ensures that in this subsequence all the south values which occur first are smaller than the one which occurs next.
What's the catch?
To get the non overlapping bridges, we need to ensure that for any two bridges, both north and south coordinates of the bridge occurring first should be smaller (or greater) than that of the bridge occurring second.
Since we have already sorted the bridges on the basis of North bank coordinates; this ensures that at least one out of two coordinates satisfy the above conditions, which is that the north bank's coordinates of the bridge occurring first is smaller than that of the bridge occurring next.
So, if we want to find the number of bridges which are not overlapping then we need to find the longest increasing subsequence of the south bank's coordinates which will ensure that both the coordinates of the bridge occurring first are smaller than the bridge occurring next.
For more clarity of this part, watch the video.
Let's try to code this!
public static class Bridge implements Comparable< Bridge > {
int n;
int s;
Bridge (int n, int s){
this.n = n;
this.s = s;
}
public int compareTo(Bridge o){
if(this.n != o.n){
return this.n - o.n;
} else {
return this.s - o.s;
}
}
}
java;
true";
First of all it's necessary that we create a class Bridge with two data members n (north) and s (south) and a constructor, so that we can store both the north and south coordinates and also access them with ease.
Then we implement a comparable interface so that we can sort the bridges on the basis of north bank coordinates (n).
If any of the two bridges have the same north bank coordinate then we sort them on the basis of south bank coordinates.
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Bridge[] brdgs = new Bridge[n];
for (int i = 0; i < brdgs.length; i++) {
String str = br.readLine();
brdgs[i] = new Bridge();
brdgs[i].n = Integer.parseInt(str.split(" ")[0]);
brdgs[i].s = Integer.parseInt(str.split(" ")[1]);
}
java;
true";
Above code snippet shows how to take input.
We take a number n and create an array of type Bridge of size n.
Then run a for loop for on array length and in each iteration we define a new bridge at ith position of the array and then take input for its north and south coordinates.
Arrays.sort(brdgs);
After that we apply sort on the array. And this sort will happen on the basis of the north bank coordinates because of the changes made to the comparable interface in Bridge class.
int[] list = new int[brdgs.length];
for(int i = 0; i < brdgs.length; i++){
Integer max = null;
for(int j = 0; j < i; j++){
if(brdgs[j].s <= brdgs[i].s){
if(max == null || lis[j] > max){
max = lis[j];
}
}
}
if(max != null){
lis[i] = max + 1;
} else {
lis[i] = 1;
}
}
int omax = 0;
for(int i = 0; i < brdgs.length; i++){
if(lis[i] > omax){
omax = lis[i];
}
}
System.out.println(omax);
java;
true";
And then we finally apply LIS on the south bank coordinates. Our result will be the same as the overall max (omax) of the LIS. So we will print omax at last.
For more clarity on this part, watch the video underneath.
Analysis
Time Complexity
O(n^2)
A nested for loop is used 2 times and a single for loop once, which condenses to O(n^2).
Space Complexity
O(n)
Two n sized arrays are used which condenses to O(n).
Complete Code:
import java.io.*;
import java.util.*;
public class Main {
public static class Bridge implements Comparable {
int n;
int s;
public int compareTo(Bridge o){
if(this.n != o.n){
return this.n - o.n;
} else {
return this.s - o.s;
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Bridge[] brdgs = new Bridge[n];
for (int i = 0; i < brdgs.length; i++) {
String str = br.readLine();
brdgs[i] = new Bridge();
brdgs[i].n = Integer.parseInt(str.split(" ")[0]);
brdgs[i].s = Integer.parseInt(str.split(" ")[1]);
}
Arrays.sort(brdgs);
int[] lis = new int[brdgs.length];
for(int i = 0; i < brdgs.length; i++){
Integer max = null;
for(int j = 0; j < i; j++){
if(brdgs[j].s <= brdgs[i].s){
if(max == null || lis[j] > max){
max = lis[j];
}
}
}
if(max != null){
lis[i] = max + 1;
} else {
lis[i] = 1;
}
}
int omax = 0;
for(int i = 0; i < brdgs.length; i++){
if(lis[i] > omax){
omax = lis[i];
}
}
System.out.println(omax);
}
}
java;
true";
We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.
Trust me it will just get easier to understand after you have watched the solution video.
You can contact us via our website. Doubts, suggestions and feedback are always welcomed.
It is also advised that you follow the sequence of modules and questions which is there on our website.
Keep practicing more and more problems daily. Meditate enough on each step of each problem.
All the best for an exciting future! Happy Coding!
