You are given a number n, representing the number of envelopes.
You are given n pair of numbers, representing the width and height of each envelope.
You are required to print the count of the maximum number of envelopes that can be nested
inside each other.
Rotation is not allowed.
Reader, meditate on the fact that to nestle envelope 1 in envelope 2, the width and height of
envelope 1 should be strictly lesser than that of envelope 2.
As we have studied in "Maximum Non-overlapping Bridges", we are going to sort the width and
apply "LIS" (Longest Increasing Subsequence) on the height.
On performing these two actions, the widths as well as the heights will get arranged in an
increasing order.
We obtain the longest subsequence by applying "LIS", which gives us the maximum number of nested
envelopes.
HOW
Now we discuss how to code this problem using the above approach and its prerequisites.
We create a class Envelope which implements Comparable and has 2 data members, "w" (width)
and "h" (height).
Since we want to sort the envelopes on the basis of the width, we write a compareTo()
function for the same.
In case you don't know how Comparable interface is used, we suggest you watch the following
video.
The number of envelopes, n is taken as an input and an array of type Envelope is formed of
size n.
Next, for each of these envelopes, we take their width and height as the input and set them
in the array "envlps" against their corresponding index.
As discussed in the approach, we sort the array "envlps" on the basis of their widths ( by
using the Comparable interface in the class Envelope).
Now we make an array "dp" which is the same size as "envlps" for applying LIS on heights.
We check if the height and width of the first envelope is strictly smaller than that of the
second envelope. If this condition is true, only then can they be nested. This check is
mainly done so that envelopes of the same dimensions are not allowed to nest.
Now we compare the value of dp[i] with the overall max and change the value of overall max
if needed.
The final value of "omax" obtained at last is printed.
import java.io.*;
import java.util.*;
public class Main {
public static class Envelope implements Comparable{ //1
int w;
int h;
Envelope(int w, int h){
this.w=w;
this.h=h;
}
public int compareTo(Envelope o){ //1
return this.w-o.w;
}
}
public static void main(String[] args) throws Exception {
Scanner scn=new Scanner(System.in);
int n=Integer.parseInt(scn.nextLine()); //2
Envelope[]envlps=new Envelope[n];
for(int i=0;i < n;i++){ //3 String line=scn.nextLine(); String[] parts=line.split(" ");
int w=Integer.parseInt(parts[0]);
int h=Integer.parseInt(parts[1]);
envlps[i]=new Envelope(w,h);
}
Arrays.sort(envlps); //4
int[]dp=new int[n]; //5
int omax=0; //omax=overall max
for(int i=0;i < dp.length;i++){
int max=0;
for(int j=0;j < i;j++){
if(envlps[j].h < envlps[i].h && envlps[j].w < envlps[i].w){ //6
if(dp[j] > max){
max=dp[j];
}
}
}
dp[i]=max+1;
if(dp[i] > omax){ //7
omax=dp[i];
}
}
System.out.println(omax); //8
}
}
java;
true" ;
Now that we have reached the end of this discussion, we again request you to watch
the pre- requisite videos mentioned earlier in case you get stuck anywhere.
You can also watch the solution video of "Russian Doll Envelopes" for
resolving any other issues.
